D. Modulo maths

Birute loves modular arithmetics, but hates long problem statements.

$\text{[math]}$

Given n, find f(n).

Input

The first line contains the number of test cases T (T ≤ 50). In the following T lines there are integer values of number n (1 ≤ n ≤ 10007).

Output

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the value of f(n).

Examples

Input

2
1
2

Output

Case #1: 1
Case #2: 0

Note

Fun fact: 1 is neither prime nor composite number.

虽然是D题，但是有点水。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <set>
 6 #define N 10007
 7 // #define M 2005
 8 // #define inf 8e18
 9 #define ll long long int
10 using namespace std;
11 int k[N];
12 void prime(){
13   memset(k,0,sizeof(k));
14   for(int i=2;i<=N;i++){
15     if(!k[i]){
16       for(int j=2;j*i<=N;j++)
17         k[i*j]=1;
18     }
19   }
20 }
21 ll pow_mod(ll a,ll b,ll mo)
22 {
23     ll ans=1;
24     a%=mo;
25     while (b){
26         if (b&1)
27           ans=(ans*a)%mo;
28         b>>=1;
29         a=a*a%mo;
30     }
31     return ans%mo;
32 }
33 int main(){
34     ll n,m;
35     cin>>n;
36     int t=1;
37     prime();
38     while(n--){
39       cin>>m;
40       if(m==1)
41         cout<<"Case #"<<t<<": "<<1<<endl;
42       else if(!k[m]){
43         cout<<"Case #"<<t<<": "<<pow_mod(2,m-1,m)<<endl;
44       }else{
45         cout<<"Case #"<<t<<": "<<(((m-1)%m)*((m-1)%m))%m<<endl;
46       }
47       t++;
48     }
49   return 0;
50 }