题解

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int num) {
    if (num <= 1)
        return false;
    if (num <= 3)
        return true;
    if (num % 2 == 0 || num % 3 == 0)
        return false;
    
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    
    return true;
}

int mp(int start, int target) {
    if (start == target)
        return 0;
    
    queue<int> q;
    unordered_set<int> visited;
    
    q.push(start);
    visited.insert(start);
    
    int steps = 0;
    
    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; ++i) {
            int curr = q.front();
            q.pop();
            
            string currStr = to_string(curr);
            
            for (int j = 0; j < 4; ++j) {
                char originalDigit = currStr[j];
                
                for (char newDigit = '0'; newDigit <= '9'; ++newDigit) {
                    if (j == 0 && newDigit == '0') // Avoid leading zeros
                        continue;
                    
                    currStr[j] = newDigit;
                    int newNum = stoi(currStr);
                    
                    if (newNum == target)
                        return steps + 1;
                    
                    if (isPrime(newNum) && visited.find(newNum) == visited.end()) {
                        q.push(newNum);
                        visited.insert(newNum);
                    }
                }
                
                currStr[j] = originalDigit;
            }
        }
        
        steps++;
    }
    
    return 0;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int a, b;
        cin >> a >> b;
        
        int result = mp(a, b);
        cout << result << endl;
    }
    
    return 0;
}