#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int dist[10000];
void bfs(string a, string b) {
	queue<string> q;
	q.push(a);
	while (!q.empty()) {
		string a = q.front();
		q.pop();
		for (int i = 0;i < a.size();i++) {

			for (int j = 0;j <= 9;j++) {
				if (i != 0 || j != 0) {
					string na = a;
					if (na[i] - '0' != j) {
						na[i] = j + '0';
						bool check = true;
						int temp = stoi(na);
						for (int i = 2;i*i <= temp;i++) {
							if (temp % i == 0) {
								check = false;
							}
						}
						if (check&&dist[temp] == -1) {
							dist[temp] = dist[stoi(a)] + 1;
							q.push(na);
						}
					}
				}
			}
		}
	}
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		string a, b;
		cin >> a >> b;
		memset(dist, -1, sizeof(dist));
		dist[stoi(a)] = 0;

		bfs(a, b);
		if (dist[stoi(b)] == -1) {
			cout << "Impossible" << endl;
		}
		else {
			cout << dist[stoi(b)] << endl;
		}
	}
	return 0;
}