1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 const int maxn=200010;
 6 int lens,lent,Q,p,cas;
 7 int f[maxn],r[maxn];
 8 char s[maxn],t[maxn];
 9 struct ExKmp{
10     void Init(){
11         memset(f,0,sizeof(f));
12         memset(r,0,sizeof(r));
13         s[lens+1]=‘%‘;t[lent+1]=‘&‘;
14     }
15     
16     void Get_Fail(){
17         f[1]=lent;
18         while(t[2+f[2]]==t[1+f[2]])
19             f[2]+=1;p=2;
20         for(int i=3;i<=lent;i++){
21             int k=p+f[p]-1,L=f[i-p+1];
22             if(i+L-1<k)f[i]=L;
23             else{
24                 f[i]=max(0,k-i+1);
25                 while(t[1+f[i]]==t[i+f[i]])
26                     f[i]+=1;p=i;
27             }
28         }    
29     }
30     
31     void Exkmp(){
32         Init();Get_Fail();
33         while(s[1+r[1]]==t[1+r[1]])
34             r[1]++;p=1;
35         for(int i=2;i<=lens;i++){
36             int k=p+r[p]-1,L=f[i-p+1];
37             if(i+L-1<k)r[i]=L;
38             else{
39                 r[i]=max(0,k-i+1);
40                 while(t[1+r[i]]==s[i+r[i]])
41                     r[i]+=1;p=i;
42             }
43         }    
44     }
45 }kmp;
46 
47 int fail[maxn];
48 int Get_Rnd(){
49     fail[1]=fail[2]=1;
50     for(int i=2;i<=lent;i++){
51         int j=fail[i];
52         while(j!=1&&t[i]!=t[j])j=fail[j];
53         fail[i+1]=t[i]==t[j]?j+1:1;
54     }
55     if(lent-fail[lent]==0||lent%(lent-fail[lent]))
56         return 1;
57     else 
58         return lent/(lent-fail[lent]);
59 }
60 
61 void Solve(){
62     kmp.Exkmp();
63     int rnd=Get_Rnd();
64     int ans1=0,ans2=0,ans3=0;
65     for(int i=1;i<=lent;i++){
66         if(r[i]==lent)ans2++;
67         else if(s[i+r[i]]<t[r[i]+1])ans1++;
68         else if(s[i+r[i]]>t[r[i]+1])ans3++;
69     }
70     printf("%d %d %d\n",ans1/rnd,ans2/rnd,ans3/rnd);
71 }
72 
73 int main(){
74     scanf("%d",&Q);
75     while(Q--){
76         scanf("%s",t+1);
77         lent=strlen(t+1);
78         for(int i=1;i<=lent;i++)
79             s[i]=s[lent+i]=t[i];
80         printf("Case %d:",++cas);
81         lens=lent*2;Solve();
82     }    
83     return 0;
84 }