1  #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<queue>
  6 #include<set>
  7 #include<math.h>
  8 using namespace std;
  9 typedef long long LL;
 10 typedef struct node
 11 {
 12         LL m[4][4];
 13         node()
 14         {
 15                 memset(m,0,sizeof(m));
 16         }
 17 } maxtr;
 18 int f1[1000];
 19 int f2[1000];
 20 maxtr E();
 21 void Init(maxtr *q);
 22 maxtr quick_m(maxtr ans,LL n,LL mod);
 23 LL quick(LL n,LL m,LL mod);
 24 bool prime[1000005];
 25 int aa[1000005];
 26 int oula[1000005];
 27 
 28 int main(void)
 29 {
 30         int T;
 31         int __ca = 0;
 32         int i,j;
 33         int k1,k2;
 34         f1[2] = 0;
 35         f1[3] = 1;
 36         f2[2] = 1;
 37         f2[3] = 1;
 38         for(i = 2; i < 1000; i++)
 39         {
 40                 for(j = i; (i*j) <= 1000000; j++)
 41                 {
 42                         prime[i*j] = true;
 43                 }
 44         }
 45         int cn = 0;
 46         for(i = 2; i <= 1000000; i++)
 47         {
 48                 oula[i] =i;
 49                 if(!prime[i])
 50                         aa[cn++] = i;
 51         }
 52         for(i = 0; i < cn; i++)
 53         {
 54                 for(j = 1; (j*aa[i])<=1000000; j++)
 55                 {
 56                         oula[j*aa[i]]/=aa[i];
 57                         oula[j*aa[i]]*=(aa[i]-1);
 58                 }
 59         }
 60         for(i = 4;; i++)
 61         {
 62                 f1[i] = f1[i-1]+f1[i-2];
 63                 if(f1[i] > 1000000)
 64                 {
 65                         k1 = i;
 66                         break;
 67                 }
 68         }
 69         for(i = 4;; i++)
 70         {
 71                 f2[i] = f2[i-1] + f2[i-2];
 72                 if(f2[i] > 1000000)
 73                 {
 74                         k2 = i;
 75                         break;
 76                 }
 77         }
 78         k1=max(k1,k2);
 79         scanf("%d",&T);
 80         while(T--)
 81         {
 82                 __ca++;
 83                 LL n,p,a,b;
 84                 scanf("%lld %lld %lld %lld",&a,&b,&p,&n);
 85                 printf("Case #%d: ",__ca);
 86                 if(n==1)
 87                 {
 88                         printf("%lld\n",a%p);
 89                 }
 90                 else if(n == 2)
 91                 {
 92                         printf("%lld\n",b%p);
 93                 }
 94                 else if(n == 3)
 95                 {
 96                         printf("%lld\n",a*b%p);
 97                 }
 98                 else  if(n<=k1)
 99                 {
100                         int x1 = f1[n];
101                         int x2 = f2[n];
102                         LL ask = quick(a,x1,p);
103                         LL ack = quick(b,x2,p);
104                         printf("%lld\n",ask*ack%p);
105                 }
106                 else
107                 {
108                         if(p==1)printf("0\n");
109                         else
110                         {
111                                 maxtr cc ;
112                                 Init(&cc);
113                                 cc = quick_m(cc,n-3,oula[p]);
114                                 LL xx = cc.m[0][0] +cc.m[0][1];
115                                 LL yy = cc.m[1][0] + cc.m[1][1];
116                                 LL ask = quick(a,yy+oula[p],p)*quick(b,xx+oula[p],p)%p;
117                                 printf("%lld\n",ask);
118                         }
119                 }
120         }
121         return 0;
122 }
123 maxtr E()
124 {
125         maxtr e;
126         for(int i = 0; i < 4; i++)
127         {
128                 for(int j = 0; j < 4; j++)
129                 {
130                         if(i == j)
131                                 e.m[i][j] = 1;
132                 }
133         }
134         return e;
135 }
136 void Init(maxtr *q)
137 {
138         q->m[0][0] = 1;
139         q->m[0][1] = 1;
140         q->m[1][0] = 1;
141         q->m[1][1] = 0;
142 }
143 maxtr quick_m(maxtr ans,LL n,LL mod)
144 {
145         int i,j,s;
146         maxtr ak = E();
147         while(n)
148         {
149                 if(n&1)
150                 {
151                         maxtr c;
152                         for(i = 0; i < 2; i++)
153                         {
154                                 for(j = 0; j < 2; j++)
155                                 {
156                                         for(s = 0; s < 2; s++)
157                                         {
158                                                 c.m[i][j] = c.m[i][j] + ans.m[i][s]*ak.m[s][j]%mod;
159                                                 c.m[i][j]%=mod;
160                                         }
161                                 }
162                         }
163                         ak = c;
164                 }
165                 maxtr d;
166                 for(i = 0; i < 2; i++)
167                 {
168                         for(j = 0; j < 2; j++)
169                         {
170                                 for(s= 0; s < 2; s++)
171                                 {
172                                         d.m[i][j] = d.m[i][j] + ans.m[i][s]*ans.m[s][j]%mod;
173                                         d.m[i][j]%=mod;
174                                 }
175                         }
176                 }
177                 ans = d;
178                 n>>=1;
179         }
180         return ak;
181 }
182 LL quick(LL n,LL m,LL mod)
183 {
184         LL ak = 1;
185         while(m)
186         {
187                 if(m&1)
188                         ak = ak*n%mod;
189                 n = n*n%mod;
190                 m>>=1;
191         }
192         return ak;
193 }