1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int T,M,N,K,I,a,b,c,ans,cnt, head, tail;
int visit[10000];
queue<int> que;
void init(){
  memset(visit, 0, sizeof(visit));
  cin >> head >> tail;
  que.push(head);
  visit[head] = 1;
}
stringstream ss;
string str,ts;
void sol(){
  int x, num;
  if(tail != head)
  while(!que.empty()){
    x = que.front();
    que.pop();
    ss.clear();
    ss << x;
    ss >> str;
    for(int i=0;i<10;i++){
      for(int j=0;j<4;j++)if(str[j]-'0' != i){
        ts = str;
        ts[j] = '0'+i;
        ss.clear();
        ss << ts;
        ss >> num;
        if(num == tail){
          cout << visit[x] << endl;
          while(!que.empty()) que.pop();
          return;
        }
        if(!visit[num] && is_pr(num)){
          visit[num] = visit[x]+1;
          que.push(num);
        }
      }
    }
  }
  cout << 0 << endl;
}
int main(){
  build();
  cin >> T;
  while(T--){
    init();
    sol();
  }
}