new

//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
int v[1000];
int q[1000];
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++)
    {
		int hi = 0;
        string s;
        cin>>s;
        cout<<"Case #"<<p<<":";
        p++;
        int cons=0;
        int vowel=0;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]=='A' || s[i]=='E' || s[i]=='I' || s[i]=='O' || s[i]=='U')
            {
                vowel++;
            }
            else
            {
                cons++;
            }
        }
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]=='Q')
            {
                v[0]=1+v[0];
            }
            if(s[i]=='W')
            {
                v[1]=1+v[1];
            }
            if(s[i]=='R')
            {
                v[3]=1+v[3];
            }
            if(s[i]=='T')
            {
                v[4]=1+v[4];
            }
            if(s[i]=='Y')
            {
                v[5]=1+v[5];
            }
            if(s[i]=='P')
            {
                v[9]=1+v[9];
            }
            if(s[i]=='S')
            {
                v[11]=1+v[11];
            }
            if(s[i]=='D')
            {
                v[12]=1+v[12];
            }
            if(s[i]=='F')
            {
                v[13]=1+v[13];
            }
            if(s[i]=='G')
            {
                v[14]=1+v[14];
            }
            if(s[i]=='H')
            {
                v[15]=1+v[15];
            }
            if(s[i]=='J')
            {
                v[16]=1+v[16];
            }
            if(s[i]=='K')
            {
                v[17]=1+v[17];
            }
            if(s[i]=='L')
            {
                v[18]=1+v[18];
            }
            if(s[i]=='Z')
            {
                v[19]=1+v[19];
            }
            if(s[i]=='X')
            {
                v[20]=1+v[20];
            }
            if(s[i]=='C')
            {
                v[21]=1+v[21];
            }
            if(s[i]=='V')
            {
                v[22]=1+v[22];
            }
            if(s[i]=='B')
            {
                v[23]=1+v[23];
            }
            if(s[i]=='N')
            {
                v[24]=1+v[24];
            }
            if(s[i]=='M')
            {
                v[25]=1+v[25];
            }
        }
        int mp=0;
        for(int i=0; i<26; i++)
        {
            if(v[i]>=hi)
            {
                hi=v[i];
            }
        }
        int a=0,e=0,I=0,o=0,u=0;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]=='A')
            {
                q[0]=q[0]+1;
            }
            else if(s[i]=='E')
            {
                q[1]=q[1]+1;
            }
            else if(s[i]=='I')
            {
                q[2]=q[2]+1;
            }
            else if(s[i]=='O')
            {
                q[3]=q[3]+1;
            }
            else if(s[i]=='U')
            {
                q[4]=q[4]+1;
            }

        }
        int bye=0;
        for(int i=0; i<26; i++)
        {
            if(q[i]>=bye)
            {
                bye=q[i];
            }
        }
        for(int i=0; i<26; i++)
        {
            if(v[i]>mp)
            {
                mp=v[i];
            }
        }
        int c2=(cons-mp);
        int c3=(c2*2)+vowel;
        int v1=vowel-bye;
        int v2=(v1*2)+cons;
        cout<<min(c3,v2)<<endl;
        for(int i=0; i<26; i++)
        {
            v[i]=0;
        }
        for(int i=0; i<26; i++)
        {
            q[i]=0;
        }
    }
}