#include<bits/stdc++.h>                  
#include<ext/pb_ds/assoc_container.hpp>   
#include<ext/pb_ds/tree_policy.hpp>       
#define ll long long                      
#define ld long double                   
using namespace std;                    
using namespace __gnu_pbds;

ll ans=0;
ll n,k;
typedef struct node{
	ll cnt=0;
	 node* ch[26];	

	}trie;
		
struct node* root;

void insert(string &s) 		
{
 struct node* cur = root;
 ll N= s.length();
 ll z;
 for(ll i=0;i<N;i++)
 {
   z = (ll)(s[i]) -(ll) ('A');
 // cout<<"::::::: "<<z<<endl;
 if(cur->ch[z])
 {
//	cout<<"+++++"<<endl;
	cur=cur->ch[z];
 }
 else
 {
	// cout<<"#######"<<endl;
  struct node* newnode = (struct node*)malloc(sizeof(struct node)) ;
  cur->ch[z]=newnode;
  cur=newnode;	 
 // cur->cnt++;
 }
 	  
 }
	cur->cnt = cur->cnt + 1;
	//cout<<cur->cnt<<" "<<z<<endl;
}

void dfs(struct node* cur,ll lvl)
{
  
	for(ll i=0;i<26;i++)
	{
//	cout<<lvl<<"  "<<i<<"  ";		
	if(cur->ch[i]!=NULL)
	{
	//  cout<<"S"<<endl;
	  dfs(cur->ch[i],lvl+1);
	  cur->cnt += cur->ch[i]->cnt;
	}
	
	}
	// cout<<"yoo"<<" "<<lvl<<" "<<cur->cnt<<endl;
	while(cur->cnt>=k && cur!=NULL)
	{
	cur->cnt-=k;
	ans+=lvl;	
	
	}
	return;
}


// void print(struct node*cn)
// {
// for(ll i=0;i<26;i++)
// {
// if(cn->ch[i])
// {
// cout<<i<<" ";	
// }	
// }
// return;	
// }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.flush();
	ll t=1;
	ll CaseN=1; 
	cin>>t;
	while(t--)
	{
		
		ans=0;
		cin>>n>>k;
		root = (struct node*)malloc(sizeof(struct node));
		for(ll i=0;i<n;i++)
		{
		string s;
		cin>>s;
		insert(s);	
		}
		dfs(root,0);
	//	print(root);
		cout<<"Case #"<<CaseN<<": ";
		CaseN++;
		// print your ans below;
		cout<<ans<<endl;
	}

return 0;
}