prime_path.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 10000;
bool is_prime[MAXN];

void buildSieve() {

    fill(is_prime, is_prime + MAXN, true);

    is_prime[0] = false;
    is_prime[1] = false;

    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i]) {

            for (int j = i * i; j < MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int bfs (int src, int dest) {

    if (src == dest) return 0;

    vector<int> dist((size_t)MAXN, -1);
    dist[(size_t)src] = 0;

    queue<int> q;
    q.push(src);

    while (!q.empty()) {

        int cur = q.front();
        q.pop();

        int d[4];
        d[0] = cur / 1000;
        d[1] = cur / 100 % 10;
        d[2] = cur / 10 % 10;
        d[3] = cur % 10;

        for (int pos = 0; pos < 4; pos++) {
            int original = d[pos];

            for (int digit = 0; digit <= 9; digit++) {

                if (pos == 0 && digit == 0) continue;

                if (digit == original) continue;

                d[pos] = digit;
                int next = d[0] * 1000 + d[1] * 100 + d[2] * 10 + d[3];

                if (is_prime[next] && dist[(size_t)next] == -1) {
                    dist[(size_t)next] = dist[(size_t)cur] + 1;

                    if (next == dest) return dist[(size_t)next];

                    q.push(next);
                }
            }
            d[pos] = original;
        }
    }
    return -1;
}

int main() {

    buildSieve();

    int T;
    cin >> T;

    while (T--) {
        int src, dest;
        cin >> src >> dest;

        int result = bfs(src, dest);
        if (result == -1) cout << "Impossible" << endl;
        else cout << result << endl;
    }
    return 0;
}