Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

Output

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

Source Code

• Source Code
•   1#include <iostream>
    2#include <math.h>
    3#include <queue>
    4#include <stdio.h>
    5
    6using namespace::std;
    7
    8int cnumber[10000];
    9
   10bool mark[10000];
   11
   12
   13bool isprimer(int npp)
   14{
   15    for (int q = 2; q <= sqrt(double(npp)); ++q)
   16    {
   17        if (npp % q == 0)
   18        {
   19            return 0;
   20        }
   21    }
   22    return 1;
   23
   24}
   25
   26
   27int main()
   28{
   29
   30//    freopen("1.txt","r",stdin);
   31
   32    int n;
   33    cin >> n;
   34
   35    while (n)
   36    {
   37        queue<int> number;
   38        int x;
   39        int y;
   40        int i;
   41        int j;
   42        int newnumber;
   43
   44        memset(cnumber,0,sizeof(cnumber));
   45        memset(mark,0,sizeof(mark));
   46        
   47        cin >> x >> y;
   48
   49
   50        cnumber[x] = 0;
   51
   52        number.push(x);
   53
   54        while (number.size())
   55        {
   56            newnumber = number.front();
   57
   58            int p = (newnumber % 1000) / 100;
   59
   60            int p1 = newnumber % 1000 % 100 / 10;
   61
   62            number.pop();
   63
   64            mark[newnumber] = 1;
   65    
   66            if (newnumber == y)
   67            {
   68                break;
   69            }
   70
   71            int num;
   72            
   73            for (i = 0; i <= 9; ++i)
   74            {
   75                num = newnumber % 1000 + i * 1000;
   76
   77                
   78                if (i != 0 && mark[num] != 1 && isprimer(num))
   79                {
   80                    number.push(num);
   81                    cnumber[num] = cnumber[newnumber] + 1;  
   82                    mark[num] = 1;
   83                }
   84        
   85                int num1;
   86                num1 = newnumber - p * 100 + i * 100;
   87
   88
   89                if (mark[num1] != 1 && isprimer(num1))
   90                {
   91
   92                    number.push(num1);
   93                    cnumber[num1] = cnumber[newnumber] + 1; 
   94                    mark[num1] = 1;
   95                }
   96                int num2;
   97                num2 = newnumber - p1 * 10 + i * 10;
   98
   99
  100                if (mark[num2] != 1 &&  isprimer(num2))
  101                {
  102                    number.push(num2);
  103                    cnumber[num2] = cnumber[newnumber] + 1; 
  104                    mark[num2] = 1;
  105                }
  106
  107                int num3 = newnumber / 10 * 10 + i;
  108    
  109                if (mark[num3] != 1 &&  isprimer(num3))
  110                {
  111                    number.push(num3);
  112                    cnumber[num3] = cnumber[newnumber] + 1; 
  113                    mark[num3] = 1;
  114                }
  115            }
  116            
  117        }
  118
  119        cout << cnumber[y] << endl;
  120
  121        n--;
  122    }
  123
  124    return 0;
  125}
  126