> #include <iostream>
> #include <queue>
> #include <math.h>
> 
> using namespace std;
> int isprime(int m)
> {
> 	for(int i = 2; i*i <= m; i++)
> 		if(m % i == 0) return 0;
> 	return 1;
>  } 
> void BFS(int n,int k)
> {
> 	int vis[10005] = {0};
> 	int step[10005];
> 	queue <int> q;
> 	int head,end;
> 	q.push(n);
> 	vis[n] = 1;
> 	step[n] = 0;
> 	while(!q.empty()){
> 		head = q.front();
> 		q.pop();
> 		for(int i = 0; i < 4; ++i){
> 			for(int j = 0; j <= 9; ++j){ //一开始本人 写成了 i<9 结果又重写了另一个算法 然后发现我这错了 我擦 傻了  
> 				if(i == 3 && j == 0) continue;
> 				if(i == 0 ) end = (head/10)*10 + j;
> 				else if(i == 1 ) end = (head/100)*100+head%10+j*10;
> 				else if(i == 2 ) end = (head/1000)*1000+head%100+j*10*10;
> 				else if(i == 3 ) end = head%1000 + j*1000;
> 				int max = k/1000;
> 				if(!vis[end] && isprime(end)){ //原本想加end1000<max来剪枝的，然后又debug半天发现不能 服了 
> 					q.push(end);
> 					vis[end] = 1;
> 					step[end] = step[head] + 1;
> 					if(end == k){
> 						cout << step[end] << endl;
> 						return;
> 					}
> 				}
> 			}
> 		}
> 	}
> 	cout << "Impossible\n"; //我还忘了有impossible 然后又。 服了服了 
> }
> int main()
> {
> 	int T;cin >> T;
> 	while(T--){
> 		int n,k;
> 		cin >> n >> k;
> 		if(n == k) cout << 0 << endl;
> 		else BFS(n,k);
> 	}
> }