#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
int u=1;
while(t--)
{
int n,k,maxm=0;
cin>>n>>k;
cout<<"Case "<<u++<<":"<<endl;
map<string ,int> m;
queue<string> q;
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;
}