#include<bits/stdc++.h>
using namespace std;

#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cout<<#x " = "<<(x)<<endl
#define DBG         pf("Hi\n")
#define pf          printf
#define pii         pair <int, int>
#define pll         pair <LL, LL>
#define pb          push_back
#define PI          acos(-1.00)
#define sz          size()
#define xx          first
#define yy          second
#define eps         1e-9
#define MAX         100000

typedef long long int LL;
typedef double db;
char s[MAX+10];
bool taken[MAX+10];
int len;
queue<int> q;
bool check(int mid)
{
    int f = 0;
    int i, cnt = 0;
    mem(taken,0);
    while(!q.empty())
        q.pop();
    for(i = 0; i<len; i++)
    {
        if(s[i] == '^')
            q.push(i);
        else
        {
            if(!q.empty())
                taken[q.front()] = 1, q.pop(), cnt++, taken[i] = 1;
        }
        if(cnt == mid)
            break;
    }
    if(cnt < mid)
        return 0;
    cnt = 0;
    int takeNext = 0;
    for(i = 0; i<len; i++)
    {
        if(s[i] == '_' && taken[i])
            takeNext++;
        else if(s[i] == '^' && !taken[i] && takeNext)
            cnt++, takeNext--;
    }
    return (cnt >= mid);
}
int main()
{
    int i, j, k, cs, t;
    sf(t);
    FRE(cs,1,t)
    {
        scanf("%s",s);
        len = strlen(s);
        int lo = 0, hi = len, mid;
        while(lo < hi)
        {
            mid = (lo+hi+1)/2;
            if(check(mid))
                lo = mid;
            else
                hi = mid-1;
        }
        pf("Case %d: %d\n",cs,lo);
    }
    return 0;
}