#include<iostream>
#include<string>
#include<queue>
using namespace std;
int p1, p2;
string s1, s2;
int vis[10000];
struct node
{
	string pri;
	int times;
};
bool isprime(int p)
{
	for (int i = 2; i <= p / i; i++)
		if (p%i == 0)
			return true;
	return false;
}
int bfs()
{
	node p;
	queue<node> arr;
	p.pri = s1;
	p.times = 0;
	arr.push(p);
	while (!arr.empty())
	{
		
		node s = arr.front();
		//cout << s.pri << endl;
		arr.pop();
		if (s.pri == s2)
		{
			return s.times;
		}
		for (int i = 0; i < 4; i++)
		{
			node temp;
			string t;
			t = s.pri;
			if (i == 0)
			{
				for (int j = 1; j <= 9; j++)
				{
					t[i] = j + '0';
					if (!isprime(atoi(t.c_str())) && !vis[atoi(t.c_str())])
					{
						temp.pri = t;
						temp.times = s.times + 1;
						vis[atoi(t.c_str())] = 1;
						arr.push(temp);
					}
				}
			}
			else
			{
				for (int j = 0; j <= 9; j++)
				{
					t[i] = j + '0';
					if (!isprime(atoi(t.c_str())) && !vis[atoi(t.c_str())])
					{
						temp.pri = t;
						temp.times = s.times + 1;
						vis[atoi(t.c_str())] = 1;
						arr.push(temp);
					}
				}
			}
		}
	}
	return -1;
}
int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		memset(vis, 0, sizeof(vis));
		cin >> s1 >> s2;
		p1 = atoi(s1.c_str());
		p2 = atoi(s2.c_str());
		vis[p1] = 1;
		int res = bfs();
		if (res == -1)
			cout << "Impossible" << endl;
		else
			cout << res << endl;
	}
	
	return 0;
}