Trie_2

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

#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<endl
#define pb push_back
#define mp make_pair

const int mod = (int)1e9+7;

struct node{
    int  endmark;
    node *next[5];
    node(){
        endmark = 0;
        for(int i=0; i<5; i++){
            next[i] = 0;
        }
    }
} *root ;

map< string , int > MAP;
int mx ;

void   _insert(string str){
    node *cur = root;
    int cnt = 0 ;
    string s="";
    for(int i=0; i<str.size(); i++){
        char ch  = str[i];
        int x;
        if(ch=='A') {x = 0 ; }
        else if(ch=='C') {x = 1 ; }
        else if(ch == 'G') {x = 2 ; }
        else if(ch == 'T'){x = 3 ; }
        if(cur->next[x]==0 ){
            cur->next[x] = new node();
        }
        cur = cur->next[x];
        cur->endmark++;
        int temp = (i+1)*cur->endmark;
        mx = max(mx,temp);
    }
}

void del(node *cur){
    for(int i=0; i<5; i++){
        if(cur->next[i]){
            del(cur->next[i]);
        }
    }
    delete(cur);
}

bool cmp(string str1,string str2){
    return str1.size()<str2.size() ;
    return str1>str2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    int tc  = 0;
    while(t--){
        root = new node();
        string str;
        int n;
        cin>>n;
        vector< string > vec;
        map<string,int>::iterator it;
        bool flag = false;
        for(int i=0; i<n; i++){
            cin>>str;
            vec.push_back(str);
        }
        //sort(vec.begin(),vec.end(),cmp);
        mx = -1000000000;
        for(int i=0; i<vec.size(); i++){
                _insert(vec[i] );
        }
        printf("Case %d: %d\n",++tc,mx);
        del(root);
    }
    return 0;
}