原题如下

内阁大臣非常沮丧，他收到了安全部长的消息：他们都需要改变办公室的四位房间号码。

安全部长：经常换换房间号码是出于安全方面的考虑，可以让敌人陷入迷惑。

内阁大臣：但是我选择1033作为我的房间号是出于我个人的偏爱。我可是内阁大臣。

安全部长：你不就是喜欢素数吗？我们给你安排了8179 这个号码，你只需要贴四个新数字覆盖住以前的四个老数字就可以了。

内阁大臣：不行，没有那么容易。当我把 1033的 1用8 盖住的时候，8033可不是个素数！

安全部长：我知道，你不能允许你的门上出现非素数。

内阁大臣：正确！所以我必须找到一个方法从1033 修改到8179，使得过程中门上出现的永远是素数，而且每次只能够修改当前数字的一位。

这个时候，在旁边偷听的财政大臣忍不住来插嘴。

财政大臣：千万不要为了这个事情增加不必要的开支！我知道换一个数字就是要花一磅！

内阁大臣：那我需要一个懂计算机的人来帮我规划一下。

信息大臣：我能够帮助你！

信息大臣现在把这个任务就交给你了。你要从一个四位数的素数出发，每次修改其中的一位，并且要保证修改的结果还是一个素数，还不能出现前导零。你要找到一个修改次数最少的方案，得到我们所需要的素数。

关于 1033 怎么变到 8179，这里是一个最短的方策： 1033 1733 3733 3739 3779 8779 8179 修改了 6次，所以要花6 磅。

Format Input

第一行给出一个正整数：测试用例的数目（最多100）。每个测试用例一行，两个用空格分开的数字，这两个数字都是4位素数（不以0作为首位）。

Output

对于每个测试用例，输出一行，或者是最小花费的数目，或者输出Impossible。

Samples

输入数据 1 3 1033 8179 1373 8017 1033 1033 输出数据 1 6 7 0 Limitation 1s, 1024KiB for each test case.

代码如下

# include <bits/stdc++.h>
#include <cstring>
using namespace std;
struct stu
{
    string str;
    int num;
};
int n;
string str1,str2;
map <string,bool> mp[105];
queue <stu> q,p;
bool check(string str)
{
    int m=0;
    for (int u=0;u<4;u++)
    {
        m=m*10+(str[u]-'0');
    }
    for (int u=2;u*u<=m;u++)
        if (m%u==0)
            return false;
    return true;
}
void bfs(int x)
{
    q=p;
    q.push((stu){str1,0});
    mp[x][str1]=1;
    while (!q.empty())
    {
        stu p=q.front();
        q.pop();
        if (p.str==str2)
        {
            cout<<p.num<<'\n';
            return ;
        }
        for (int u=0;u<4;u++)
        {
            p.str[u]=char(p.str[u]+1);
            if (p.str[0]!='0'&&p.str[u]>='0'&&p.str[u]<='9'&&!mp[x][p.str]&&check(p.str))
            {
                mp[x][p.str]=1;
                q.push((stu){p.str,p.num+1});
            }
            p.str[u]=char(p.str[u]-2);
            if (p.str[0]!='0'&&p.str[u]>='0'&&p.str[u]<='9'&&!mp[x][p.str]&&check(p.str))
            {
                mp[x][p.str]=1;
                q.push((stu){p.str,p.num+1});
            }
            p.str[u]=char(p.str[u]+1);
        }
    }
    cout<<"Impossible"<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int u=1;u<=n;u++)
    {
        cin>>str1>>str2;
        bfs(u);
    }

    return 0;
}