1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 char a[2000005];
 8 bool flag[2000002];
 9 int s1[2000004];
10 typedef struct
11 {
12     int num;
13     int sum;
14 } Queue;
15 Queue q[2000004],tmp;
16 int tom;
17 
18 int main()
19 {
20     int T,t;
21     int i,k,n,len,tail,head;
22     while(scanf("%d",&T)>0)
23     {
24         getchar();
25         for(t=1; t<=T; t++)
26         {
27             scanf("%s",a+1);
28             n=strlen(a+1);
29             len=n+n;
30             for(i=n+1; i<=len; i++)
31                 a[i]=a[i-n];
32             for( s1[0]=0,i=1; i<=len; i++)
33             {
34                 if(a[i]==‘C‘) s1[i]=s1[i-1]+1;
35                 else s1[i]=s1[i-1]-1;
36             }
37             memset(flag,false, sizeof(flag));
38             head=0;
39             tail=-1;
40             for(i=1; i<=len-1; i++)
41             {
42                 tmp.sum=s1[i];
43                 tmp.num=i;
44                 while( head<=tail && q[tail].sum>tmp.sum ) tail--;
45                 q[++tail]=tmp;
46                 if( i>=n )
47                 {
48                     while( head<=tail && q[head].num+n<=i ) head++;
49                     if( q[head].sum-s1[i-n]>=0 )
50                     {
51                         flag[ i-n+1 ]=true;
52                     //    printf("%d ",i-n+1);
53                     }
54                 }
55             }
56         //    printf("\n");
57             s1[0]=0;
58             for(i=1; i<=len; i++)
59             {
60                 k=len-i+1;
61                 if(a[k]==‘C‘) s1[i]=s1[i-1]+1;
62                 else s1[i]=s1[i-1]-1;
63             }
64             head=0;tail=-1;
65             for(i=1; i<=len; i++)
66             {
67                 tmp.sum=s1[i];
68                 tmp.num=i;
69                 while( head<=tail && q[tail].sum>tmp.sum ) tail--;
70                 q[++tail]=tmp;
71                 if( i>n )
72                 {
73                     while( head<=tail && q[head].num+n<=i ) head++;
74                     if( q[head].sum-s1[i-n]>=0 )
75                     {
76                         flag[ n-(i-n)+1 ]=true;
77                     //    printf("%d ",n-(i-n)+1);
78                     }
79                 }
80             }
81         //    printf("\n");
82             for(tom=0,i=1; i<=n; i++)
83                 if(flag[i]==true) tom++;
84             printf("Case %d: %d\n",t,tom);
85         }
86     }
87     return 0;
88 }