题解（中速）

可以把每次变换视为一个点，因为求的是最少变换路径，所以可以利用广度优先搜索来求解，不必把a和b视为整数，把它们当做字符串更方便

#include<bits/stdc++.h>
using namespace std;

string s,t;
struct node
{
	string num;
	int step;
};
bool isp[10005];
map<string,int> vis;
bool prime(int x)
{
	if (x%2==0) return 0;
	for (int i=3;i<=sqrt(x);i+=2)
	{
		if (x%i==0)
			return 0;
	}
	return 1;
}
void bfs()
{
	queue<node> q;
	q.push(node{s,0});
	vis[s]=1;
	while (!q.empty())
	{
		string ns=q.front().num;
		int nstep=q.front().step;
		q.pop();
		if (ns==t)
		{
			cout << nstep << endl;
			return;
		}
		for (int i=0;i<=3;i++)
		{
			for (char j='0';j<='9';j++)
			{
				string ss=ns;
				if (ss[i]==j || i==0 && j=='0' || i==3 && j%2==0) continue;
				ss[i]=j;
				if (isp[stoi(ss)] && !vis[ss])
				{
					vis[ss]=1;
					q.push({ss,nstep+1});
				}
			}
		}
	}
	cout << 0 << endl;
	return;
}
int main()
{
    int T;
    cin >> T;
    for (int i=1000;i<=9999;i++)
    	isp[i]=prime(i);
    while (T--)
    {
    	cin >> s >> t;
    	bfs();
        vis.clear();
    }
	return 0;
}