using namespace std;
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdio>
#include <set>
#include <cctype>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
#include <stack>
#include <cctype>
#include <cstring>
#include <string>

#define MAX 100100
#define PRIME 31
#define MOD 1000000007
#define PI 3.1415926535897932384
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
typedef long long ll;

int f(){
    string str;
    cin >> str;

    int acm[3] = {0, 0, 0}; // available ^ // _ // completed ^_^
    int notUsed = 0; // _ not used

    for(int i = 0;i < str.size();i++){
        if(str[i] == '^'){
            if(acm[1]){ acm[1]--; acm[2]++; } // complete ^_^
            else if(notUsed){ acm[1]++; notUsed--; } // Use a ^ already in a ^_^ to pair with _ and current ^ to fill ^_^
            else acm[0]++; // Can't complete any ^_^
        }
        else if(acm[0]) { acm[1]++; acm[0]--; } // Pair ^_
        else notUsed = min(notUsed+1, acm[2]); // Count the ^_^ which can have the second ^ replaced
    }

    return acm[2];
}

int main(){
    //freopen("in.txt", "r", stdin);

    int t;
    cin >> t;

    for(int test = 1;test <= t;test++){
        printf("Case %d: %d\n", test, f());
    }

    return 0;
}