题目链接:http://poj.org/problem?id=3126
Time Limit: 1000MS Memory Limit: 65536K

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. 
— It is a matter of security to change such things every now and then, to keep the enemy in the dark. 
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! 
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. 
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! 
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. 
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime. 

Now, the minister of finance, who had been eavesdropping, intervened. 
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. 
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? 
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above. 

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

Problem solving report:

Description: 给定两个素数n和m，要求把n变成m，每次变换时只能变一个数字，即变换后的数与变换前的数只有一个数字不同，并且要保证变换后的四位数也是素数。求最小的变换次数；如果不能完成变换，输出Impossible。
Problem solving: 首先打印素数表，由于只有四位数，直接枚举不会超时。由于要求的是“最少步数”，所以用BFS进行搜索。

Accepted Code:

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 1e4 + 5;
bool isp[MAXN], vis[MAXN];
int pre[MAXN];
struct edge {
    int a[4], t;
    edge(int *a_, int t_) {
        t = t_;
        if (a_) memcpy(a, a_, 4 * sizeof(int));
    }
}q(NULL, 0);
void prime() {
    int cnt = 0;
    memset(isp, false, sizeof(isp));
    for (int i = 2; i < MAXN; i++) {
        if (!isp[i])
            pre[cnt++] = i;
        for (int j = 0; j < cnt && i * pre[j] < MAXN; j++) {
            isp[i * pre[j]] = true;
            if (!(i % pre[j]))
                break;
        }
    }
}
int *Split(int x) {
    int *p = (int *)malloc(4 * sizeof(int));
    for (int i = 3; i >= 0; i--) {
        p[i] = x % 10;
        x /= 10;
    }
    return p;
}
int Merge(int *a) {
    int ans = 0;
    for (int i = 0; i < 4; i++)
        ans = ans * 10 + a[i];
    return ans;
}
int BFS(int m, int n) {
    int num;
    queue <edge> Q;
    memset(vis, false, sizeof(vis));
    vis[m] = true;
    Q.push(edge(Split(m), 0));
    while (!Q.empty()) {
        edge p = Q.front();
        Q.pop();
        if (Merge(p.a) == n)
            return p.t;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                if (p.a[i] != j && (i || j)) {
                    q = p;
                    q.a[i] = j;
                    q.t = p.t + 1;
                    num = Merge(q.a);
                    if (!isp[num] && !vis[num]) {
                        Q.push(q);
                        vis[num] = true;
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    prime();
    int t, m, n, ans;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &n);
        ans = BFS(m, n);
        if (~ans)
            printf("%d\n", ans);
        else printf("Impossible\n");
    }
    return 0;
}