> 代码:
> #include <iostream>
> #include <cmath>
> #include <cstdlib>
> #include <cstring>
> #include <algorithm>
> #include <vector>
> #include <string>
> #include <deque>
> #include <queue>
> #include <utility>
> #include <iterator>
> 
> using namespace std;
> const int Maxn = 10005;
> int T;
> bool isprime[Maxn];
> bool vis[Maxn];
> typedef pair < string, int> node;
> 
> string a, b;
> 
> inline void prime_sieve(int n) {
> 	memset(isprime, 1, sizeof isprime);
> 	int i, j;
> 	isprime[0] = 0, isprime[1] = 0;
> 	for (i = 2; i <= n; ++i) {
> 		if (isprime[i])
> 			for (j = i + i; j <= n; j += i)
> 				isprime[j] = 0;
> 	}
> }
> 
> inline int strtonum(string x) {
> 	int num = 0, i;
> 	if (x[0] == '-') {
> 		for (i = 1; i < x.length(); ++i)
> 			num = num * 10 + (x[i] - '0');
> 		return -num;
> 	}
> 	for (i = 0; i < x.length(); ++i)
> 		num = num * 10 + (x[i] - '0');
> 	return num;
> }
> 
> inline bool check(int num) {
> 	if (num == strtonum(b)|| (num & 1 && isprime[num] && vis[num] == 0 && num >= 0 && num <= 9999))
> 		return true;
> 	return false;
> }
> 
> inline int bfs() {
> 
> 	queue < node > Q;
> 	node x;
> 	x.first = a, x.second = 0;
> 	Q.push(x);
> 	vis[strtonum(x.first)] = 1;
> 
> 	int i, j, numberx;
> 	node next;
> 	while (!Q.empty()) {
> 		x = Q.front(); Q.pop();
> 		if (x.first == b) return x.second;
> 		for (i = 0; i < 4; ++i) {
> 			if (i == 0) {
> 				for (j = 1; j <= 9; ++j) {
> 					next = x;
> 					next.first[0] = (j + '0');
> 					numberx = strtonum(next.first);
> 					if (check(numberx)) {
> 						vis[numberx] = 1;
> 						next.second = x.second + 1;
> 						Q.push(next);
> 					}
> 				}
> 			} else if (i == 1) {
> 				for (j = 0; j <= 9; ++j) {
> 					next = x;
> 					next.first[1] = (j + '0');
> 					numberx = strtonum(next.first);
> 					if (check(numberx)) {
> 						vis[numberx] = 1;
> 						next.second = x.second + 1;
> 						Q.push(next);
> 					}
> 				}
> 			} else if (i == 2) {
> 				for (j = 0; j <= 9; ++j) {
> 					next = x;
> 					next.first[2] = (j + '0');
> 					numberx = strtonum(next.first);
> 					if (check(numberx)) {
> 						vis[numberx] = 1;
> 						next.second = x.second + 1;
> 						Q.push(next);
> 					}
> 				}
> 			} else if (i == 3) {
> 				for (j = 1; j <= 9; j += 2) {
> 					next = x;
> 					next.first[3] = (j + '0');
> 					numberx = strtonum(next.first);
> 					if (check(numberx)) {
> 						vis[numberx] = 1;
> 						next.second = x.second + 1;
> 						Q.push(next);
> 					}
> 				}
> 			}
> 		}
> 	}
> 	return -1;
> }
> 
> int main() {
> 	ios::sync_with_stdio(false);
> 	prime_sieve(Maxn);
> 	cin >> T;
> 	while (T--) {
> 		memset(vis, 0, sizeof vis);
> 		cin >> a >> b;
> 		int X;
> 		X = bfs();
> 		if (X == -1) cout << "Impossible" << endl;
> 		else cout << X << endl;
> 	}
> 	return 0;
> }
> 诡异啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。