【题目链接】click here~~

【题目大意】给你n,m各自是素数，求由n到m变化的步骤数，规定每一步仅仅能改变个十百千一位的数，且变化得到的每个数也为素数

【解题思路】和poj 3278类似。bfs+queue,分别枚举个十百千的每一位就能够了，只是注意个位仅仅能为奇数，且千位从1開始

代码：

#ifndef _GLIBCXX_NO_ASSERT

#include <cassert>

#endif

#include <cctype>

#include <cerrno>

#include <cfloat>

#include <ciso646>

#include <climits>

#include <clocale>

#include <cmath>

#include <csetjmp>

#include <csignal>

#include <cstdarg>

#include <cstddef>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#if __cplusplus >= 201103L

#include <ccomplex>

#include <cfenv>

#include <cinttypes>

#include <cstdalign>

#include <cstdbool>

#include <cstdint>

#include <ctgmath>

#include <cwchar>

#include <cwctype>

#endif

// C++

#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <iterator>

#include <limits>

#include <list>

#include <locale>

#include <map>

#include <memory>

#include <new>

#include <numeric>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <typeinfo>

#include <utility>

#include <valarray>

#include <vector>

#if __cplusplus >= 201103L

#include <array>

#include <atomic>

#include <chrono>

#include <condition_variable>

#include <forward_list>

#include <future>

#include <initializer_list>

#include <mutex>

#include <random>

#include <ratio>

#include <regex>

#include <scoped_allocator>

#include <system_error>

#include <thread>

#include <tuple>

#include <typeindex>

#include <type_traits>

#include <unordered_map>

#include <unordered_set>

#endif

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)

#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)

#define lowbit(a) a&-a

#define Max(a,b) a>b?

a:b

#define Min(a,b) a>b?

b:a

#define mem(a,b) memset(a,b,sizeof(a))

typedef long long LL;

typedef unsigned long long LLU;

typedef double db;

const int N=15000;

const int inf=0x3f3f3f3f;

int n,m,T;

bool vis[N];

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int dir6[6][3]= {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};///六个方向

inline LL read()

{

    int c=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    return c*f;

}

bool isPrime(int t)///素数推断

{

    for(int i=2; i<=sqrt(t); ++i)

        if(t%i==0) return false;

    return true;

}

struct node

{

    int val,step;

};

void bfs()

{

    mem(vis,false);

    node a,b;

    a.val=n;

    a.step=0;

    queue<node >vall;

    vall.push(a);

    while(!vall.empty()){

        a=vall.front();

        vall.pop();

        if(a.val==m){

            printf("%d\n",a.step);

            return ;

        }

        int ge=a.val%10;///枚举个位

        int shi=a.val%100/10;///枚举十位

        for(int i=1; i<=9; i+=2){///个位

            int y=(a.val/10)*10+i;

            if(y!=a.val&&isPrime(y)&&!vis[y]){

                b.val=y;

                b.step=a.step+1;

                vis[y]=1;

                vall.push(b);

            }

        }

        for(int i=0; i<=9; i++){///十位

            int y=(a.val/100)*100+i*10+ge;

            if(y!=a.val&&isPrime(y)&&!vis[y]){

                b.val=y;

                b.step=a.step+1;

                vis[y]=1;

                vall.push(b);

            }

        }

        for(int i=0; i<=9; i++){///百位

            int y=(a.val/1000)*1000+i*100+ge+shi*10;

            if(y!=a.val&&isPrime(y)&&!vis[y]){

                b.val=y;

                b.step=a.step+1;

                vis[y]=1;

                vall.push(b);

            }

        }

        for(int i=1; i<=9; i++){///千位

            int y=a.val%1000+i*1000;

            if(y!=a.val&&isPrime(y)&&!vis[y]){

                b.val=y;

                b.step=a.step+1;

                vis[y]=1;

                vall.push(b);

            }

        }

    }

    puts("Impossible");

    return ;

}

int main()

{

    T=read();

    while(T--)

    {

        n=read(),m=read();

        if(n==m) puts("0");

        else bfs();

    }

    return 0;

}

/*

Sample Input

3

1033 8179

1373 8017

1033 1033

Sample Output

6

7

0

*/