//                                        nEro
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
const ll inf = 1e18;
const int N = 2 * 1e5 + 10;

ll n, k;
ll res;
ll a[N];
ll dp[N];

string s[N];

vector<string> v;

long long segtree[4 * N];

void build(int l , int r , int node){
    if(l == r){
        segtree[node] = s[l].size();
    }
    else{
        int mid = l + r >> 1;
        build(l , mid , node + node);
        build(mid + 1 , r , node + node + 1);
        ll can = min(segtree[node + node], segtree[node + node + 1]);
        ll ans = 0;
        for(int i = 0; i < can; ++i){
            if(s[mid][i] != s[mid + 1][i])    break;
            ++ans;
        }
        segtree[node] = ans;
    }
}

long long query(int l , int r , int node , int ql , int qr){
    if(l > qr || r < ql){
        return inf;
    }
    if(l >= ql && r <= qr){
        return segtree[node];
    }
    int mid = l + r >> 1;
    ll xx = query(l , mid , node + node , ql , qr);
    ll yy = query(mid + 1 , r , node + node + 1 , ql , qr);
    if(xx == inf)   return yy;
    if(yy == inf)   return xx;
    ll can = min(xx, yy);
    ll ans = 0;
    for(int i = 0; i < can; ++i){
        if(s[mid][i] != s[mid + 1][i])    break;
        ++ans;
    }
    return ans;
}

bool ok(ll m, ll n){
    for(int i = 1; i <= n; ++i){
        if(i + k - 1 <= n){
            if(query(1, n, 1, i, i + k - 1) >= m)   return true;
        }
    }
    return false;
}

void solve(){
    ll ans = 0, gg = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
        gg = max(gg, (ll)s[i].size());
    }
    sort(s + 1, s + n + 1);
    ll cur = n;
    while(cur){
        ll lo = -1, hi = gg + 1;
        build(1, cur, 1);
        while(lo + 1 < hi){
            ll m = lo + hi >> 1LL;
            if(ok(m, cur))   lo = m;
            else    hi = m;
        }
        if(lo <= 0) break;   
        for(int i = 1; i <= cur; ++i){
            if(i + k - 1 <= cur){
                if(query(1, cur, 1, i, i + k - 1) == lo){
                    ans += lo;
                    i += (k - 1);
                }
                else    v.push_back(s[i]);
            }
            else    v.push_back(s[i]);
        }
        for(int i = 1; i <= v.size(); ++i){
            s[i] = v[i - 1];
        }
        cur = v.size();
        v.clear();
        gg = lo - 1;
    }

    cout << "Case #" << ++res << ": " << ans << "\n";
}
 
int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    ll t = 1;
    cin >> t;
    while(t--){
        solve();
        v.clear();
    }
}
//                                        orEn