#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 10000
bool prime[MAX];

// 优化的素数打表函数
void init() {
    // 初始化所有数为素数
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    
    // 埃拉托斯特尼筛法优化版
    for (int i = 2; i * i < MAX; i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                prime[j] = false;
            }
        }
    }
}

int bfs(int first, int last) {
    bool dis[MAX];
    queue<int> q;
    int count1[MAX];
    
    // 初始化距离数组和访问数组
    memset(dis, false, sizeof(dis));
    memset(count1, 0, sizeof(count1));
    
    q.push(first);
    dis[first] = true;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        // 提前退出：如果当前就是目标数
        if (v == last) {
            return count1[v];
        }
        
        // 分解四位数字
        int t[4];
        t[0] = v / 1000;
        t[1] = v % 1000 / 100;
        t[2] = v % 100 / 10;
        t[3] = v % 10;
        
        for (int j = 0; j < 4; j++) {
            int temp = t[j];
            for (int i = 0; i < 10; i++) {
                if (i != temp) {
                    t[j] = i;
                    int vtemp = t[0] * 1000 + t[1] * 100 + t[2] * 10 + t[3];
                    
                    // 检查是否是有效四位素数且未访问过
                    if (vtemp >= 1000 && !dis[vtemp] && prime[vtemp]) {
                        count1[vtemp] = count1[v] + 1;
                        dis[vtemp] = true;
                        q.push(vtemp);
                        
                        // 找到目标时立即返回
                        if (vtemp == last) {
                            return count1[vtemp];
                        }
                    }
                }
            }
            t[j] = temp; // 还原数字
        }
    }
    
    return -1; // 无法到达
}

int main() {
    int st, ed, n;
    init(); // 初始化素数表
    
    cin >> n;
    while (n--) {
        cin >> st >> ed;
        int ans = bfs(st, ed);
        if (ans != -1) {
            cout << ans << endl;
        } else {
            cout << "Impossible" << endl;
        }
    }
    return 0;
}
这个问题本质上是一个图搜索问题，我们需要找到从一个四位素数到另一个四位素数的最短路径，每次只能改变一个数字且每次改变后必须仍然是素数。最适合的解决方案是使用广度优先搜索 (BFS)，因为 BFS 能保证找到最短路径。

首先，我们需要解决两个关键问题：

如何高效判断四位数字是否为素数
如何使用 BFS 找到最短转换路径