//3126
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<bitset>

using namespace std;

bool isPrime(int num)
{
	int t = sqrt(static_cast<double>(num)) + 1;
	int i;
	for(i = 2; i <= t; ++i)
	{
		if(num % i == 0)
		{
			return false;
		}
	}
	if(i > t)
		return true;
	else
		return false;
}

int main(int argc, char* argv[])
{
	queue<int> q;
	int one,two,count,front;
	int n,i,tmp,t;
	bitset<10000> bt;
	for(i = 1001; i < 10000; ++i)
	{
		if(isPrime(i))
			bt.set(i);
	}
	bitset<10000> search;

	cin>>n;
	//cin.get();
	//for(i = 0; i < n; ++i)
	while(n > 0)
	{
		cin>>one>>two;
		
		if(!isPrime(one) || !isPrime(two))
		{
			cout<<"Impossible"<<endl;
			--n;
			continue;
		}
		if(one == two)
		{
			cout<<"0"<<endl;
			--n;
			continue;
		}

		count = 0;
		search.set(one);
		q.push(one);
		q.push(-1);
		while(count <= 1061)
		{
			front = q.front();
			q.pop();
			if(front == -1)
			{
				++count;
				q.push(-1);
				continue;
			}
			if(front == two)
			{
				cout<<count<<endl;
				break;
			}
			
			tmp = front - front % 10;
			for(i = 1; i < 10; i += 2)
			{
				t = tmp + i;
				if( t != front && bt.test(t) && !search.test(t))
				{
					q.push(t);
					search.set(t);
				}
			}

			tmp = front - front%100 + front % 10;
			for(i = 0; i < 10; ++i)
			{
				t = tmp + i * 10;
				if(t != front && bt.test(t) && !search.test(t))
				{
					q.push(t);
					search.set(t);
				}
			}

			tmp = front - front%1000 + front%100;
			for(i = 0; i < 10; ++i)
			{
				t = tmp + i * 100;
				if(t != front && bt.test(t) && !search.test(t))
				{
					q.push(t);
					search.set(t);
				}
			}

			tmp = front%1000;
			for(i = 1; i < 10; ++i)
			{
				t = tmp + i * 1000;
				if(t != front && bt.test(t) && !search.test(t))
				{
					q.push(t);
					search.set(t);
				}
			}
		}
		if(count > 1061)
			cout<<"Impossible"<<endl;
		search.reset();
		while(!q.empty())
			q.pop();
		--n;
	}
	return 0;
}

• Re:60纪念，对宽搜一直只操作一个队列，不知道算不算土方法，不过时间还好，G++ 16Ms (8) asuran 2009-10-11 03:25:18