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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
const ll mod = 1e9+7;

struct trie{
    int cnt;
    bool eow;
    map<char,trie*> mp;
    trie(){
        cnt = 0;
        eow = false;
    }
};
void build(trie* root, string &s){

    for(int i=0;i<s.length();++i){
        if(root->mp[s[i]] == NULL){
            root->mp[s[i]] = new trie();
        }
        root = root->mp[s[i]];
        ++root->cnt;
    }
    root->eow = true;
}
int ans = 0;
int fun(trie* root, int k, int lvl){

    if (root->cnt < k)
        return 0;

    int f = 0;
    for(auto &p:root->mp){
        f+=fun(p.second,k,lvl+1);
    }


    if(root->cnt>=k){
        ans += lvl*((root->cnt-f)/k);

    }

    return f+k*((root->cnt-f)/k);
}
// void fun(trie* root, int k, int lvl){
//     // cout<<root->cnt<<endl;
//     if (root==NULL)
//         return ;
//     // cout<<"__"<<root->cnt<<endl;
//     int f = 0;
//     for(auto &p:root->mp){
//         fun(p.second,k,lvl+1);
//     }
//     // root->cnt -= f;

//     if(root->cnt>=k){
//         ans += root->cnt/k;
//         // cout<<"__"<<root->cnt<<"->"<<lvl*(root->cnt/k)<<" f:"<<f<<endl;
//     }
// }
int g = 1;
int solve(){
    ll n,k;cin>>n>>k;
    vector<string> a(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    trie *root = new trie();

    for(int i=0;i<n;++i){
        build(root,a[i]);
    }
    for(auto &p:root->mp){
        // cout<<"\n------------------\n";
        fun(p.second,k,1);
    }
    cout<<"Case #"<<g<<": "<<ans<<endl;
    ++g;
    return 0;
}
int main(){
    fast;
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}