/*https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/A1*/
#include<bits/stdc++.h>
using  namespace  std;

#define endl         "\n"
#define ll           long long
#define PI           acos(-1.0)
#define GCD(a,b)     __gcd(a , b)
#define LCM(a,b)     ((a/__gcd(a,b))*b)
#define READ(f)      freopen(f,"r",stdin)
#define WRITE(f)     freopen(f,"w",stdout)
#define test         cout<<"\n*************\n"
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define precise(c)   fixed(cout);cout<<setprecision(c)
#define valid(x,y)   (x>=0 && x<row && y>=0 && y<column)
#define fast         ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)



int main(){

    READ("consistency_chapter_1_input.txt");
    WRITE("out.txt");

    ll t;
    cin>>t;
    ll count = 1;
    while(t--){

        string str;
        cin>>str;

        ll vow = 0,conso = 0;
        map<char,ll> vowel,consonant;

        for(ll i=0; i < str.size(); i++){
            if(str[i]=='A' || str[i]=='E' || str[i]=='I' || str[i]=='O' || str[i]=='U'){
                vow++;
                vowel[str[i]]++;
            } else{
                conso++;
                consonant[str[i]]++;
            }
        }

        ll biggest_vowel = 0;
        for(auto it = vowel.begin();it!=vowel.end();it++){
            if(it->second>biggest_vowel){
                biggest_vowel = it->second;
            }
        }

        ll biggest_consonant = 0;
        for(auto it = consonant.begin();it!=consonant.end();it++){
            if(it->second>biggest_consonant){
                biggest_consonant = it->second;
            }
        }

        if((vowel.empty() && consonant.size()==1) || (consonant.empty() && vowel.size()==1)){

            cout<<"Case #"<<count<<": " <<0<<endl;

        } else{

            ll vowel_to_conso = vow + (conso - biggest_consonant) * 2;
            ll conso_to_vowel = conso + (vow - biggest_vowel) * 2;

            cout << "Case #" << count << ": " <<min(vowel_to_conso,conso_to_vowel)<< endl;
        }

        count++;
    }

    return 0;
}