//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
int main()
{

    freopen ("in.txt", "r", stdin);

    freopen ("out.txt", "w", stdout);
    int T;
    cin >> T;
    int p=1;
    for(int tc=0; tc<T; tc++)
    {

        string s;
        cin>>s;
        cout<<"Case #"<<p<<":";
        p++;
        int cons=0;
        int vowel=0;
        int count[26];
        int hi = 0,bye = 0;
        int mp = 0;
        fill(count,count + 26,0);

        for (int i = 0; i < (int) s.size(); ++i) {
			count[s[i] - 'A']++;
			if (s[i] == 'A' or s[i] == 'E' or s[i] == 'I' or s[i] == 'O' or s[i] == 'U') {
				++vowel;
				bye = max(bye,count[s[i] - 'A']);
			} else {
				++cons;
				hi = max(hi,count[s[i] - 'A']);
			}
		}
		mp = hi;
        int c2=(cons-mp);
        int c3=(c2*2)+vowel;
        int v1=vowel-bye;
        int v2=(v1*2)+cons;
        cout<<min(c3,v2)<<endl;
    }
}