114 lines
2.4 KiB
C++
114 lines
2.4 KiB
C++
#include <iostream>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <cstdio>
|
|
#include <queue>
|
|
using namespace std;
|
|
struct item
|
|
{
|
|
int num[4];
|
|
} a, b;
|
|
int prime[100], primenum, cost[10000];
|
|
int toint(item &a)
|
|
{
|
|
int ans = 0;
|
|
for (int i = 0; i < 4; i++)
|
|
ans = ans * 10 + a.num[i];
|
|
return ans;
|
|
}
|
|
void makeprime()
|
|
{
|
|
primenum = 1;
|
|
prime[0] = 2;
|
|
for (int i = 3; i < 100; i++)
|
|
{
|
|
bool ok = true;
|
|
for (int j = 0; prime[j] * prime[j] <= i; j++)
|
|
if (i % prime[j] == 0)
|
|
{
|
|
ok = false;
|
|
break;
|
|
}
|
|
if (ok)
|
|
{
|
|
prime[primenum++] = i;
|
|
}
|
|
}
|
|
}
|
|
void init()
|
|
{
|
|
memset(cost, -1, sizeof(cost));
|
|
for (int i = 0; i < 4; i++)
|
|
{
|
|
char ch;
|
|
scanf("%c", &ch);
|
|
a.num[i] = ch - '0';
|
|
}
|
|
getchar();
|
|
for (int i = 0; i < 4; i++)
|
|
{
|
|
char ch;
|
|
scanf("%c", &ch);
|
|
b.num[i] = ch - '0';
|
|
}
|
|
getchar();
|
|
}
|
|
bool isprime(int a)
|
|
{
|
|
for (int i = 0; i < primenum && prime[i] * prime[i] <= a; i++)
|
|
if (a % prime[i] == 0)
|
|
return false;
|
|
return true;
|
|
}
|
|
void work()
|
|
{
|
|
cost[toint(a)] = 0;
|
|
queue<item> q;
|
|
q.push(a);
|
|
while (!q.empty())
|
|
{
|
|
item temp = q.front();
|
|
int costnow = cost[toint(temp)];
|
|
q.pop();
|
|
for (int i = 0; i < 4; i++)
|
|
{
|
|
int x = temp.num[i];
|
|
for (int j = 0; j < 10; j++)
|
|
{
|
|
if (i == 0 && j == 0)
|
|
continue;
|
|
if (j == x)
|
|
continue;
|
|
temp.num[i] = j;
|
|
int inttemp = toint(temp);
|
|
if (cost[inttemp] == -1 && isprime(inttemp))
|
|
{
|
|
cost[inttemp] = costnow + 1;
|
|
if (inttemp == toint(b))
|
|
{
|
|
printf("%d\n", cost[inttemp]);
|
|
return;
|
|
}
|
|
q.push(temp);
|
|
}
|
|
}
|
|
temp.num[i] = x;
|
|
}
|
|
}
|
|
}
|
|
int main()
|
|
{
|
|
int t;
|
|
makeprime();
|
|
scanf("%d", &t);
|
|
getchar();
|
|
while (t--)
|
|
{
|
|
init();
|
|
if (toint(a) == toint(b))
|
|
printf("0\n");
|
|
work();
|
|
}
|
|
return 0;
|
|
}
|