> #include<cstdio>
> #include<algorithm>
> using namespace std;
> const int M=100000;
> int prime[10000],p0[10000],t[10000],b[10000];
> int gcd(int a,int b)
> {
>  if(b==0)return a;
>  return gcd(b,a%b);
> }
> int modn(int a,int b,int c)
> {
>  int ans=1;
>  while(b)
>  {
>   if(b&1)ans=(ans*a)%c;
>   a=(a*a)%c;
>   b>>=1;
>  }
>  if(ans==1)
>  return 1;
>  else return 0;
> }
> int main()
> {
>     int i,j,k,m,n,Euler,ans;
>     int q,p,two,T=1,s;
>     char ch;
>     prime[1]=2;
>     prime[2]=3;
>     k=2;
>     for(i=5;i<=M;i+=2)
>    {
>     for(j=1;prime[j]*prime[j]<=i;j++)
>     {
>       if(i%prime[j]==0)goto loop;
>     }
>     k++;prime[k]=i;
>     loop:;
>    }
>     prime[0]=k;
>     while(scanf("%d%c%d",&p,&ch,&q)!=EOF)
>     {two=0;
>      p=p/gcd(p,q);q=q/gcd(p,q);
>      
>      while(q%2==0){two++;q/=2;}
>      
>      k=0;
>      n=m=q;
>     for(i=1;i<=prime[0];i++)
>     {
>      s=0;
>      while(n%prime[i]==0){s++;n/=prime[i];}
>      if(s>0){k++;p0[k]=prime[i];t[k]=s;}
>      if(n==1)break;
> 
>      if(n/prime[i]<prime[i]){k++;p0[k]=n;t[k]=1;break;}
>    }
>     Euler=m;
>     for(i=1;i<=k;i++)
>     Euler=(Euler/p0[i]*(p0[i]-1));
>     n=Euler;
>     k=0;
>     for(i=1;i*i<=n;i++)//计算n所有的因子 
>     {if(n%i==0)
>      {
>       k++;b[k]=i;
>       if(b[k]!=n/i){k++;b[k]=n/i;} 
>      }
>     }
>     sort(b,b+k+1);
>     for(i=1;i<=k;i++)
>     printf("%d\n",b[i]);
>     for(i=1;i<=k;i++)
>     if(modn(2,b[i],q)){ans=b[i];break;}
>     printf("Case #%d: %d,%d\n",T++,two+1,ans);
> 
>     }
> }
>