#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;
	    unordered_set<string> st;
	    string s,l,p;
	    for(int i=0;i<n;i++)
	    {
	        cin>>s;
	        if(q.size()<k)
	        q.push(s);
	        else
	        {
	            p=q.front();
	            q.pop();
	            m[p]--;
	            q.push(s);
	            st.erase(p);
	            if(l==p)
	            maxm=m[p];
	        }
	        m[s]++;
	        st.insert(s);
	        if(m[s]>=maxm)
	        {
	            l=s;
	            maxm=m[s];
	        }
	        if(m[p]>=maxm)
	        {
	            maxm=m[p];
	            l=p;
	        }
	        set<string>::iterator it;
	        for(it=st.begin();it!=st.end();it++)
	        {
	            if(m[*it]==maxm)
	            {
	                l=*it;
	                break;
	            }
	        }
	        cout<<l<<" "<<maxm<<endl;
	    }
	}
	return 0;
}