#include<stdio.h>
#include<math.h>
int gcd(int a, int b)
{
if(b==0) return a ;
else
return(gcd(b,a%b)) ;
}
long long int mod(long long int a , long long int b , long long int n )
{
long long int x=1 , y=a ;
while(b>0)
{
if(b%2==1) x = ((x%n)*(y%n))%n ;
y = ((y%n)*(y%n))%n ;
b/=2 ;
}
return x%n ;
}
int isprimes(long long int u)
{
if(u==3)
return 1 ;
int a = 2 , i ;
long long int k , t = 0 , r , p ;
k = u-1 ;
while(k%2==0)
{ k/=2 ; t++ ; }
while(a<=3) /*der are no strong pseudoprimes common in base 2 and base 3*/
{
r = mod(a,k,u) ;
for(i = 1 ; i<=t ; i++)
{
p = ((r%u)*(r%u))%u ;
if((p==1)&&(r!=1)&&(r!=(u-1)))
{ return 0 ; }
r = p ;
}
if(p!=1)
return 0 ;
else
a++ ;
}
if(a==4)
return 1 ;
}
long long int pol(long long int u)
{
long long int x = 2 , k , i , a , y , c , s;
int d = 1 ;
k = 2 ;
i = 1 ;
y = x ;
a = u ;
if(isprimes(u)==1)
{
return 1;
}
c=-1 ;
s = 2 ;
while(1)
{
i++;
x=((x%u)*(x%u)-1)% u ;
if(d!=1&&d!=u)
while(a%d==0) { a=a/d; }
x = 2 ;
k = 2 ;
i = 1 ;
y = x ;
if(a==1)
{ return 0 ; }
if(isprimes(a)!=0)
{ return a ; }
u=a ;
}
if(i==k)
{y = x ; k*=2 ; c = x ;} /*floyd cycle detection*/
if(c==x)
{ x = ++s ; }
}
return ;
}
int main()
{
long long int t ;
long long int i , n , j , k , a , b , u ;
while(scanf("%lld",&n
)&&n
!=0) { u = n ; k = 0 ;
while(u%2==0)
{ u/=2 ; k = 1 ; }
if(u!=1)
t = pol(u) ;
if(u!=1)
{
if(t==1)
else
if(t!=0)
}
}
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgppbnQgZ2NkKGludCBhLCBpbnQgYikKewogICAgaWYoYj09MCkgcmV0dXJuIGEgOwogICAgZWxzZQogICAgcmV0dXJuKGdjZChiLGElYikpIDsKfQoKbG9uZyBsb25nIGludCBtb2QobG9uZyBsb25nIGludCBhICwgbG9uZyBsb25nIGludCBiICwgbG9uZyBsb25nIGludCBuICkKeyAgICAKICAgICBsb25nIGxvbmcgaW50IHg9MSAsIHk9YSA7CiAgICAgd2hpbGUoYj4wKQogICAgIHsKICAgICAgICBpZihiJTI9PTEpICB4ID0gKCh4JW4pKih5JW4pKSVuIDsKICAgICAgICB5ID0gKCh5JW4pKih5JW4pKSVuIDsKICAgICAgICAgYi89MiA7CiAgICAgfQogICAgIHJldHVybiB4JW4gOwp9CgppbnQgaXNwcmltZXMobG9uZyBsb25nIGludCB1KQp7ICAKICAgIGlmKHU9PTMpCiAgICByZXR1cm4gMSA7CiAgICAgaW50IGEgPSAyICwgaSA7CiAgICAgbG9uZyBsb25nIGludCBrICwgdCA9IDAgLCByICwgcCA7CiAgICAgayA9IHUtMSA7CiAgICAgd2hpbGUoayUyPT0wKQogICAgIHsgay89MiA7IHQrKyA7IH0KICAgCiAgICAgICAgIHdoaWxlKGE8PTMpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvKmRlciBhcmUgbm8gc3Ryb25nIHBzZXVkb3ByaW1lcyBjb21tb24gaW4gYmFzZSAyIGFuZCBiYXNlIDMqLwogICAgICAgICB7ICAgCiAgICAgICAgIHIgPSBtb2QoYSxrLHUpIDsKICAgICAgICAgICAgIGZvcihpID0gMSA7IGk8PXQgOyBpKyspCiAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgIHAgPSAoKHIldSkqKHIldSkpJXUgOwogICAgICAgICAgICAgICAgICBpZigocD09MSkmJihyIT0xKSYmKHIhPSh1LTEpKSkKICAgICAgICAgICAgICAgICAgeyAgcmV0dXJuIDAgOyB9CiAgICAgICAgICAgICAgICAgIHIgPSBwIDsKICAgICAgICAgICAgIH0KICAgICAgICAgIGlmKHAhPTEpCiAgICAgICAgICByZXR1cm4gMCA7CiAgICAgICAgIGVsc2UKICAgICAgICAgIGErKyA7CiAgICAgICAgIH0gCiAgICAgICAgIAogICAgICAgICAgaWYoYT09NCkKICAgICAgICAgIHJldHVybiAxIDsKICAgICAgCn0KICAgICAgIApsb25nIGxvbmcgaW50IHBvbChsb25nIGxvbmcgaW50IHUpCnsgCiAgbG9uZyBsb25nIGludCB4ID0gMiAsIGsgLCBpICwgYSAsIHkgLCBjICwgczsKICBpbnQgZCA9IDEgOwogICBrID0gMiA7CiAgIGkgPSAxIDsKICAgeSA9IHggOwogICBhID0gdSA7CiAgIGlmKGlzcHJpbWVzKHUpPT0xKQogICB7IAogICAgIHJldHVybiAxOwogICB9CiAgIGM9LTEgOwogICBzID0gMiA7CiAgIHdoaWxlKDEpCiAgIHsKICAgICBpKys7CiAgICAgeD0oKHgldSkqKHgldSktMSklIHUgOwogCiAgICAgZCA9IGdjZChhYnMoeS14KSx1KSA7CiAgICAKICAgICBpZihkIT0xJiZkIT11KQogICAgIHsgcHJpbnRmKCIlZCAiLGQpOwogICAgICAgd2hpbGUoYSVkPT0wKSB7IGE9YS9kOyAgfQogICAgICAgCiAgICAgICAgeCA9IDIgOwogICAgICAgIGsgPSAyIDsKICAgICAgICBpID0gMSA7CiAgICAgICAgeSA9IHggOwogICAgICAgIGlmKGE9PTEpCiAgICAgICAgeyByZXR1cm4gMCA7IH0KICAgICAgICBpZihpc3ByaW1lcyhhKSE9MCkKICAgICAgICB7IHJldHVybiBhIDsgfQogICAgICAgIHU9YSA7CiAgICAgICAKICAgICB9CiAgICAgaWYoaT09aykKICAgICB7eSA9IHggOyBrKj0yIDsgYyA9IHggO30gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLypmbG95ZCBjeWNsZSBkZXRlY3Rpb24qLwogICAgICAgIGlmKGM9PXgpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICB7IHggPSArK3MgOyB9CiAgICB9CiAgICByZXR1cm4gOwogICAgCn0KCmludCBtYWluKCkKewogICBsb25nIGxvbmcgaW50IHQgOwogICAgbG9uZyBsb25nIGludCBpICwgbiAsIGogLCBrICwgYSAsIGIgICwgdSA7CiAgICB3aGlsZShzY2FuZigiJWxsZCIsJm4pJiZuIT0wKQogICAgeyB1ID0gbiA7IGsgPSAwIDsKICAgIHdoaWxlKHUlMj09MCkKICAgICAgIHsgIHUvPTIgOyBrID0gMSA7IH0KICAgICAgaWYoaz09MSkgcHJpbnRmKCIyICIpIDsKICAgICAgaWYodSE9MSkKICAgICAgdCA9IHBvbCh1KSA7CiAgICAgICAgaWYodSE9MSkgCiAgICAgIHsKICAgICAgICAgICBpZih0PT0xKQogICAgICAgICAgIHsgcHJpbnRmKCIlbGxkIix1KSA7IH0KICAgICAgICAgICBlbHNlCiAgICAgICAgICAgaWYodCE9MCkKICAgICAgICAgICB7IHByaW50ZigiJWxsZCIsdCkgOyB9CiAgICAgIH0KICAgICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIHJldHVybiAwOwp9CiAgICAgICAgICAgICAgIAo=