/**
 * 
 * https://c...content-available-to-author-only...s.com/blog/entry/75011#comment-591464
 * 
**/


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define deb(x) cout<<#x<<" : "<<x<<"\n";
#define debug(x, y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\n";
#define ff first
#define ss second
#define ub upper_bound
#define lb lower_bound
#define all(a) (a).begin(),(a).end()
#define bs binary_search
#define sz size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define clr fflush(stdout);
//#define clr cout.flush();
#define N 100001
#define fpr(i, a, b) for(int i=a;i<b;i++)
#define fdr(i, a, b) for(int i=a;i>b;i--)
#define repp(i, a, b, d) for(int i=a;i<b;i+=d)
#define repd(i, a, b, d) for(int i=a;i>b;i-=d)
#define LLMIN LLONG_MIN
#define LLMAX LLONG_MAX
#define AKASH_PATEL ios_base::sync_with_stdio(false);
#define SVNIT_SURAT cin.tie(NULL);cout.tie(NULL);
#define mset(x, a) memset(x,a,sizeof(x));
#define nl cout<<'\n';
#define print(c) cout<<c<<'\n';
#define setp(n) cout << fixed << setprecision(n)
#define take_arr(a, n) fpr(i,0,n) cin>>a[i];
#define print_arr(a, n) for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';
#define take_mat(mat, n, m) fpr(i,0,n) fpr(j,0,m) cin>>mat[i][j];
#define set_mat(mat, n, m, k) fpr(i,0,n) fpr(j,0,m) mat[i][j]=k;
#define print_mat(dist, n, m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}

template<class T>
bool inside(T a, T b, T c) { return a <= b && b <= c; }
ll ans=0;
ll n,k;
struct trie
{
	trie *a[26];
	int weight;
	int depth;
	trie()
	{
		for(int i=0;i<26;i++)
		{
			a[i]=NULL;
		}
		weight=0;
	}
};
void *insert(string s,int wt,trie *root)
{
//	if(!root->a[curr])
//	{
//		root->a[curr]=new trie();
//	}
//    (root->a[curr]->weight)++;
//	if(idx+1!=s.size())
//	{
//		root->a[curr]=insert(s,wt,idx+1,root->a[curr]);
//	}
//	return root;
    int curr,d=1;
    fpr(i,0,s.sz)
    {
        curr=s[i]-'A';
        if(!root->a[curr])
        {
            root->a[curr]=new trie();
        }
        root=root->a[curr];
        root->weight++;
        root->depth=d++;
    }
}
int searchBest(string s,trie *root)
{
	int idx=0,curr,max=-1,n=s.size();
	while(idx<n)
	{
		curr=s[idx]-'A';
		if(!root->a[curr])
			return -1;
		max=root->a[curr]->weight;
		root=root->a[curr];
		idx++;
	}
	return max;
}
void print1(trie *root) // change here
{
	for(long i=0;i<26;i++)
	{
		if(root->a[i])
		{
			print1(root->a[i]);
		}
	}
	ans+=root->weight/k;
//	cout<<s<<'\n';
//	cout<<root->weight<<'\n';
}
int main() {
    AKASH_PATEL;
    SVNIT_SURAT;
    int t;
    cin >> t;
    fpr(tas, 1, t + 1) {
        ans=0;
        cin>>n>>k;
        trie *node=new trie();
        string s[n];
        take_arr(s,n)
        fpr(i,0,n)
        {
            insert(s[i],1,node);
        }
        print1(node); // changed here
        cout << "Case #" << tas << ": " << ans << '\n';
    }
    return 0;
}