题目

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
	int f,t,s;
}que[10010];
bool vis[10010];
int head = 1,tail = 1;
int be,en,now,times;
int o,t,h,u,flag = 0;
bool Prime(int x)
{
	for(int i = 2;i * i <= x;i++)
		if(!(x % i))
			return false;
	return true;
} 
void fen(int x)
{
	o = x % 10;
	t = x % 100 / 10;
	h = x % 1000 / 100;
	u = x / 1000;
}
int he()
{
	int res = o + t * 10 + h * 100 + u * 1000;
	return res;
}
void bfs()
{
	que[tail].f = 0;
	que[tail].t = be;
	que[tail++].s = 0;
	vis[be] = true;
	now = be;
	while(head < tail)
	{
		now = que[head].t;
		fen(now);
		for(o = 0;o <= 9;o++)
		{
			if(Prime(he()) && !vis[he()])
			{
				que[tail].f = now;
				que[tail].t = he();
				que[tail++].s = que[head].s + 1;
				vis[he()] = true;
			}
		}
		for(t = 0;t <= 9;t++)
		{
			if(Prime(he()) && !vis[he()])
			{
				que[tail].f = now;
				que[tail].t = he();
				que[tail++].s = que[head].s + 1;
				vis[he()] = true;
			}
		}
		for(h = 0;h <= 9;h++)
		{
			if(Prime(he()) && !vis[he()])
			{
				que[tail].f = now;
				que[tail].t = he();
				que[tail++].s = que[head].s + 1;
				vis[he()] = true;
			}
		}
		for(t = 1;t <= 9;t++)
		{
			if(Prime(he()) && !vis[he()])
			{
				que[tail].f = now;
				que[tail].t = he();
				que[tail++].s = que[head].s + 1;
				vis[he()] = true;
			}
		}
		if(que[tail - 1].t == en)
		{
			flag = 1;
			break;
		}	
		if(flag)
			break;
		head++;
	}
}
int main()
{	
	cin >> times;
	for(int i = 0;i < times;i++)
	{
		o = 0;
		t = 0;
		h = 0;
		u = 0;
		head = 1;
		tail = 1;
		memset(vis,false,sizeof(vis));
		cin >> be >> en;
		if(be > en)
			swap(be,en);
		bfs();
		cout << que[tail - 1].s << endl;
	}
 	return 0;
}