/*
    题意：给出一个环形链，只有两种字符C,J 
           现要统计有多少个位置，使得在该位置断开，向左或向右收集字符，收集过程中，C的个数>=J

    令第i与i+1个字符之间的间隙为第i个位置，总共可以断开n个位置，而每断开一个位置，可向右或向左
    所以用f[i]表示位置i处可行（向左或向右可行即可）

    这里只考虑向左的
    令 num[i] = str[i]=='C'?1:-1
    某个位置i可行，必须有 sum(ji] >=0 即 sum[i] - sum[j] >=0   (i-n<=j<i)
    也即只需检查 sum[i]-max{sum[j]}>=0 
    快速取得一个区间的最大值，用单调队列！
    
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 1000010;

char str[MAXN];
int sum[MAXN*2],num[MAXN*2];
int DQ[MAXN];
bool f[MAXN];

int main()
{
    //freopen("in","r",stdin);
    int T,n,t=1;
    for(scanf("%d",&T);T--;)
    {
        scanf("%s",str+1);
        n = 0;
        for(int i=1;str[i];i++,n++)
            num[i] = num[i] = (str[i]=='C'?1:-1);//很方便处理
        for(int i=1;i<=n;i++)num[i+n] = num[i];
        fill(f+1,f+1+n,false);

        int front = 0,tail = 0;
        //left to right
        //maintain a decreasing sequence
        sum[0] = 0;
        for(int i=1;i<=n;i++)
        {
            sum[i] = sum[i-1] + num[i];
            while(front<tail && sum[DQ[tail-1]] <= sum[i] )tail--;
            DQ[tail++] = i;
        }
        for(int i=n+1;i<=n+n;i++)
        {            
            sum[i] = sum[i-1] + num[i];            
            while(front<tail && DQ[front]< i-n )front++;
            if(sum[i]-sum[DQ[front]]>=0)
            {
                f[i-n] = true;
            }
            while(front<tail && sum[DQ[tail-1]] <= sum[i] )tail--;
            DQ[tail++] = i;
        }

        //right to left
        //maintain a decreasing sequence
        front = tail = 0;
        sum[n+n+1] = 0;
        for(int i=n+n;i>=n;i--)
        {
            sum[i] = sum[i+1] + num[i];
            while(front<tail && sum[DQ[tail-1]] <= sum[i] )tail--;
            DQ[tail++] = i;
        }
        for(int i=n;i>=1;i--)
        {            
            sum[i] = sum[i+1] + num[i];            
            while(front<tail && DQ[front]> i+n )front++;
            if(sum[i]-sum[DQ[front]]>=0)
            {
                if(i-1)f[i-1] = true;
                else f[n] = true;
            }
            while(front<tail && sum[DQ[tail-1]] <= sum[i] )tail--;
            DQ[tail++] = i;
        }
        
        int ans = 0;
        for(int i=1;i<=n;i++)ans += f[i];
        printf("Case %d: %d\n",t++,ans);
    }
    return 0;
}