Arcane Numbers 1

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit     

Description

Vance and Shackler like playing games. One day, they are playing a game called "arcane numbers". The game is pretty simple, Vance writes down a finite decimal under base A, and then Shackler translates it under base B. If Shackler can translate it into a finite decimal, he wins, else it will be Vance’s win. Now given A and B, please help Vance to determine whether he will win or not. Note that they are playing this game using a mystery language so that A and B may be up to 10^12.

 

Input

The first line contains a single integer T, the number of test cases. 

For each case, there’s a single line contains A and B. 

 

Output

For each case, output “NO” if Vance will win the game. Otherwise, print “YES”. See Sample Output for more details.

 

Sample Input

3 5 5 2 3 1000 2000

 

Sample Output

Case #1: YES Case #2: NO Case #3: YES

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5  6 long long gcd(long long a,long long b)  7 {  8     if(a
          
           1)29         {30             while(1)31             {32                 if(B==1)33                     break;34                 D=gcd(B,C);35                 if(D==1)36                 {37                     flg=0;38                     break;39                 }40                 B=B/D;41             }42         }43         if(A>1)44         {45             while(1)46             {47                 if(A==1)48                     break;49                 D=gcd(A,C);50                 if(D==1)51                 {52                     flg=0;53                     break;54                 }55                 A=A/D;56             }57         }58         if(flg==1)59             printf("Case #%d: YES\n",ca);60         else61             printf("Case #%d: NO\n",ca);62         ca++;63     }64     return 0;65 }