/* NWERC 2006
 * Sample solution to prime path
 * By Mikael Goldmann
 */

import java.util.*;
import java.io.*;

class Pair implements Comparable { 
    int x, y; 
    Pair(int a, int b) {x=a;y=b;} 
    public int compareTo(Object p) {
	if (x!=((Pair)p).x) return x-((Pair)p).x;
	return y-((Pair)p).y;
    }
    public boolean equals (Object p) {
	Pair q= (Pair)p;
	return x==q.x && y==q.y;
    }
	
}

public class primepath_mg {
    static final int MAX=10000;
    static boolean[] isprime = new boolean[MAX];
    static Scanner in = new Scanner(System.in);

    int shortest_path(int a, int b) 
    {
	int[] dist = new int[MAX];
	Arrays.fill(dist,-1);
	TreeSet<Pair> prio = new TreeSet<Pair>();
	dist[a]=0;
	
	int[] dig = new int[4];
	prio.add(new Pair(0,a));
	while (prio.size()>0 && dist[b]==-1) {
	    Pair p = prio.first();
	    prio.remove(p);
	    int c=p.y, d=p.y;
	    int i,j,mul;
	    for (i=0; i<4; ++i, c /= 10) dig[i] = c%10;
	    for (i=0, mul=1; i<4; ++i, mul *=10) {
		for ( j=((i<3)? 0:1); j<10 ; ++j) { // if no leading 0
		    //for ( j=0; j<10 ; ++j) {		
		    c = d + (j-dig[i])*mul;
		    if (c != d && isprime[c]) {
			if (dist[c]==-1 || dist[c]>dist[d]+j) {
			    if (dist[c] != -1) 
				prio.remove(new Pair(dist[c],c));
			    dist[c]=dist[d]+ 1 /* +j was old cost */;	  
			    prio.add(new Pair(dist[c],c));
			}
			
		    }
		}
		
	    }
	}
	return dist[b];    
    }
    
    
    void solve()throws IOException
    {
	int a=in.nextInt(),b=in.nextInt();
	int dist = shortest_path(a,b);
	if (dist>=0) System.out.println(dist);
	else System.out.println("Impossible");
    }
    
    
    
    public static void main(String[] as) throws IOException
    {
	Arrays.fill(isprime,true);
	isprime[0]=isprime[1]=false;
	for (int p=2; p*p<10000;++p)
	    if (isprime[p])
		for (int q=2*p; q < 10000; q+=p)
		    isprime[q]=false;
	int n = in.nextInt();  
	primepath_mg pp = new primepath_mg();
	while(n-->0) pp.solve();
    }
}