Description

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p = a (mod p). That is, if we raise a to the p^th power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)

Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

3 210 3341 2341 31105 21105 30 0

Sample Output

nonoyesnoyesyes 如果p是素数，输出no；如果p不是素数，判断a^p对p取余是否等于a。

1 #include
       
         2 #include
        
          3 __int64 f(__int64 a,__int64 b) 4 { 5     __int64 c=b,t=1; 6     while(b) 7     { 8         if(b % 2 != 0) 9         {10             t=t*a%c;11         }12         a=a*a%c;13         b/=2;14     }15     return t%c;16 }17 __int64 f2(__int64 a)18 {19     __int64 i;20     if(a <= 1 || a % 2 == 0) return 0;21     for(i=3;i<=sqrt(a);i++)22     {23         if(a % i == 0) return 0;24     }25     return 1;26 }27 int main()28 {29     30     __int64 p,a;31     while(scanf("%I64d %I64d",&p,&a) && p && a)32     {33         if(f2(p) == 1) printf("no\n");34         else35         {36             if(f(a,p) == a) printf("yes\n");37             else 38             printf("no\n");39         }40         41     }42 }