#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false);
	int t;
	cin>>t;
	int u=1;
	while(t--)
	{
	    int n,k,maxm=0;
	    cin>>n>>k;
	    cout<<"Case "<<u++<<":"<<endl;
	    unordered_map<string ,int> m;
	    queue<string> q;
	    set<string> v[n+1];
	    string s,l,p,prev;
	    for(int i=0;i<n;i++)
	    {
	    	cin>>s;
	        if(q.size()>=k)
	        {
	        	p=q.front();
	            q.pop();
	            v[m[p]].erase(p);
	            m[p]--;
	            if(maxm==m[p]+1)
	            {
	            	if(v[maxm].size()==0)
	            	maxm=m[p];
	            }
	            
	            v[m[p]].insert(p);
	            
	        }
	        q.push(s);
	        m[s]++;
	        v[m[s]].insert(s);
	        if(m[s]>maxm)
	        {
	        	l=s;
	            maxm=m[s];
	        }
	        if(m[p]>maxm)
	        {
	        	maxm=m[p];
	            l=p;
	        }
	     
	        set<string>::iterator it=v[maxm].begin();
	        cout<<*it<<" "<<maxm<<endl;
	    }
	}
	return 0;
}