#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;

const int maxn =10000;
int tb[maxn];
int d[maxn];
vector<int> p,arr[maxn];

void getTable(){
	for(int i=2;i*i<maxn;++i){
		if(!tb[i]){
			for(int j=i*2;j<maxn;j+=i){
				tb[j] = 1;
			}
		}
	}
	for(int i=1000;i<10000;++i){
		if(!tb[i])p.push_back(i);
	}
}

int isVaild(int x,int y){
	int diff=0;
	for(int i=0;i<4;++i){
		diff+=(x%10!=y%10);
		x/=10;y/=10;
	}
	return diff==1;
}

void getVaild(){
	for(int i=0;i<p.size();++i){
		for(int j=0;j<p.size();++j){
			if(isVaild(p[i],p[j])){
				arr[p[i]].push_back(p[j]);
			}
		}
	}
}

int bfs(int a,int b){
	if(a==b)return 0;
	queue<int> q;
	q.push(a);
	d[a]=0;
	while(q.size()){
		int x = q.front();
		q.pop();
		for(int i=0;i<arr[x].size();++i){
			int y = arr[x][i];
			if(y==b)return d[x]+1;
			if(d[y]==-1){
				d[y]=d[x]+1;
				q.push(y);
			}
		}
	}
	return -1;
}

int main(){
	getTable();
	getVaild();
	int t;
	scanf("%d",&t);
	while(t--){
		int a,b;
		scanf("%d%d",&a,&b);
		memset(d,-1,sizeof(d));
		int ret = bfs(a,b);
		if(ret==-1)printf("Impossible\n");
		else printf("%d\n",ret);
	}
	return 0;
}