#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<queue>

#include<string.h>

#define max(a, b)(a > b ? a : b)

#define min(a, b)(a < b ? a : b)

#define INF 0xffffff

#define N 10010

using namespace std;

struct node

{

    char s[];

    int step;

};

char s1[], s2[], s3[];

bool vis[N];

int prime(int n)

{

    int i, k = (int)sqrt(n);

    for(i =  ; i <= k ; i++)

        if(n % i == )

            return ;

    return ;

}

int BFS(char s[])

{

    queue<node>Q;

    node now, next;

    int i, j, h, x = ;

    memset(vis, false, sizeof(vis));

    memset(s3, , sizeof(s3));

    for(i =  ; i <  ; i++)

        x = x *  + (s[i] - '');

    vis[x] = true;

    strcpy(now.s, s);

    now.step = ;

    Q.push(now);

    while(!Q.empty())

    {

        now = Q.front();

        Q.pop();

        if(strcmp(now.s, s2) == )

            return now.step;

        for(i =  ; i <  ; i++)

        {

            for(j =  ; j <  ; j++)

            {

                if((i ==  && j == ) || now.s[i] == j + '')

                    continue;

                strcpy(s3, now.s);

                now.s[i] = j + '';

                x = ;

                for(h =  ; h <  ; h++)

                    x = x *  + (now.s[h] - '');

                if(!vis[x] && prime(x) == )

                {

                    vis[x] = true;

                    next.step = now.step + ;

                    strcpy(next.s, now.s);

                   // i = 0;

                   // j = 0;

                    Q.push(next);

                }

                strcpy(now.s, s3);

            }

        }

    }

    return -;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%s%s", s1, s2);

        printf("%d\n", BFS(s1));

    }

    return ;

}