> //6266010 on_pku 3126 Accepted 732K 16MS G++ 2214B 2009-12-21 18:18:46 
> #include<iostream>
> #include<cstdlib>
> #include<cstdio>
> #include<queue>
> using namespace std;
> const int SIZE = 10000;
> bool prime[SIZE];
> int step[SIZE];
> int base[4] = {1,10,100,1000};
> int main()
> {
>         for(int i = 0; i < SIZE; i++)prime[i] = true;
>         
>         for(int i = 2; i < SIZE; i++){
>                 if(prime[i]){
>                              for(int j = 2; i*j < SIZE; j++)
>                                      prime[i*j] = false;             
>                 }        
>         }
>         
>         int t,a,b,d[4];
>         scanf("%d",&t);
>         while(t--){
>                    scanf("%d %d",&a,&b);
>                    fill(step,step+SIZE,0);
>                    queue<int>path;
>                    path.push(a);
>                    step[a] = 1;
>                    while(!path.empty()){
>                          int ori = path.front();
>                          if(ori == b)break;
>                          path.pop();
>                          d[0] = ori%10;  d[1] = ori%100/10;
>                          d[2] = ori%1000/100;  d[3] = ori/1000;
>                          int newnum;
>                          for(int i = 0; i < 10; i ++){                                                   
>                                  newnum = ori - d[3]*1000 + i*1000;
>                                  if(i != 0 && prime[newnum] && !step[newnum]){
>                                       step[newnum] = step[ori] + 1;
>                                       path.push(newnum);               
>                                  } 
>                                  for(int k = 0; k < 3; k++){
>                                          newnum = ori - d[k]*base[k] + i*base[k];
>                                          if(prime[newnum] && !step[newnum]){
>                                               step[newnum] = step[ori] + 1;
>                                               path.push(newnum);               
>                                          }                               
>                                  }  
>                          }                     
>                    }     
>                    printf("%d\n",step[b]-1);
>         }        
>         return 0;
> }



// 8608709	lsz	3126	Accepted	288K	0MS	C++	1286B	2011-05-07 20:34:28
#include <iostream>
#include <queue>
#include <utility>
#include <complex>
using namespace std;

int main()
{
	const int N = 10000;
	const int root = (int)sqrt((double)N);
	bool not_prime[N] = {false};
	not_prime[0] = not_prime[1] = true;
	for (int i=2; i<=root; i++)
	{
		if (!not_prime[i])
		{
			for (int j=i+i; j<N; j+=i)
			{
				not_prime[j] = true;
			}
		}
	}

	const int divider[4] = {1000, 100, 10, 1};
	int n;
	cin>>n;
	while (n--)
	{
		int a, b;
		cin>>a>>b;
		if (a == b)
		{
			cout<<0<<endl;
			continue;
		}
		bool visited[N] = {false};
		queue<pair<int,int>> q;
		pair<int,int> p = pair<int,int>(a, 0);
		q.push(p);
		visited[a] = true;
		while (!q.empty() && (p = q.front()).first != b)
		{
			q.pop();
			for (int i=0; i<4; i++)
			{
				int digit = (p.first / divider[i]) % 10;
				for (int j=0; j<=9; j++)
				{
					if ((j != digit) && (i > 0 || j > 0))
					{
						int number = p.first + (j - digit) * divider[i];
						if (!visited[number] && !not_prime[number])
						{
							q.push(pair<int,int>(number, p.second + 1));
							visited[number] = true;
						}
					}
				}
			}
		}

		if (p.first == b)
		{
			cout<<p.second<<endl;
		} 
		else
		{
			cout<<-1<<endl;
		}
	}

	return 0;
}