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

先用筛法将 1000 以内的素数打表，然后 bfs 枚举每一位

import java.util.*;

public class Main {
    static int start,end;
    static TreeSet<Integer> set = new TreeSet<Integer>();
    static boolean[] vis;
    static boolean check(int a) {
        if(a > 1000 && a < 10000 && !set.contains(a) && !vis[a])
            return true;
        return false;
    }
    static void bfs() {
        Node cur,new_cur;
        cur = new Node(start,0);
        Queue<Node> q = new LinkedList<Node>();
        q.add(cur);
        vis[start] = true;
        while(!q.isEmpty()) {
            new_cur = new Node(q.peek().x,q.poll().step);
            if(new_cur.x == end) {
                System.out.println(new_cur.step);
                return;
            }
            for(int i = 0;i <= 9;i++) {
                cur = new Node(new_cur.x,new_cur.step);
                cur.x /= 10;//取出前三位
                cur.x = cur.x * 10 + i;//枚举第四位
                if(check(cur.x)) {
                    cur.step++;
                    q.add(cur);
                    vis[cur.x] = true;
                }
            }
            for(int i = 0;i <= 9;i++) {
                cur = new Node(new_cur.x,new_cur.step);
                int a = cur.x % 10;//取出最后一位
                cur.x /= 100;//取出前两位
                cur.x = cur.x * 100 + i * 10 + a;//枚举第三位
                if(check(cur.x)) {
                    cur.step++;
                    q.add(cur);
                    vis[cur.x] = true;
                }
            }
            for(int i = 0;i <= 9;i++) {
                cur = new Node(new_cur.x,new_cur.step);
                int b = cur.x % 100;//取出最后两位
                cur.x /= 1000;//取出第一位
                cur.x = cur.x * 1000 + i * 100 + b;//枚举第二位
                if(check(cur.x)) {
                    cur.step++;
                    q.add(cur);
                    vis[cur.x] = true;
                }
            }
            for(int i = 1;i <= 9;i++) {
                cur = new Node(new_cur.x,new_cur.step);
                cur.x %= 1000;//取出第一位
                cur.x = cur.x + i * 1000;//枚举第一位
                if(check(cur.x)) {
                    cur.step++;
                    q.add(cur);
                    vis[cur.x] = true;
                }
            }
        }
        System.out.println("Impossible");
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        //筛法
        for(int i = 2;i <= Math.sqrt(10000);i++) 
            if(!set.contains(i))
                for(int j = 2 * i;j < 10000;j += i)
                    set.add(j);
        int n = cin.nextInt();
        while((n--) != 0) {
            vis = new boolean[10000];
            start = cin.nextInt();
            end = cin.nextInt();
            bfs();
        }
    }
}
class Node {
    int x,step;
    Node(int x,int step) {
        this.x = x;
        this.step = step;
    }
}