static const int pows[] = {1, 10, 100, 1000};
int change(int number, int digit, int insert) {
switch (digit) {
case 0:
return number / 10 * 10 + insert;
case 1:
return number / 100 * 100 + number % 10 + insert * 10;
case 2:
return number / 1000 * 1000 + number % 100 + insert * 100;
case 3:
return number % 1000 + insert * 1000;
}
return 0;
}
#define MAX (16 * 1024)
static int dp[MAX];
int main() {
static bool flag[MAX];
memset(flag, -1, sizeof(flag));
flag[0] = flag[1] = false;
for (int i = 2; i * i < MAX; ++i){
if (!flag[i]){
continue;
}
for (int j = i * i; j < MAX; j += i){
flag[j] = false;
}
}
int N;
cin >> N;
for (int n = 0; n < N; ++n) {
fill_n(dp, MAX, INT_MAX);
int start, goal;
cin >> start >> goal;
dp[start] = 0;
deque<int> q;
q.push_back(start);
while (!q.empty()) {
const int current = q.front();
q.pop_front();
for (int digit = 0; digit < 4; ++digit) {
for (int number = 0; number < 10; ++number) {
const int next = change(current, digit, number);
if (next < 1000) {
continue;
}
if (!flag[next] || dp[next] <= dp[current]) {
continue;
}
dp[next] = dp[current] + 1;
q.push_back(next);
}
}
}
cout << dp[goal] << endl;
}
}
