#include<bits/stdc++.h>

 using namespace std;

 const int maxn=2e5;

 char s[maxn+];

 int sa[maxn+],rk[maxn+];

 int t[maxn+],t2[maxn+],c[maxn+];

 int nx[maxn+][];

 int len,k;

 queue<int> q[maxn+];

 void getsa(int m)//m表示最大字符的编码

 {

     memset(t,-,sizeof(t));

     memset(t2,-,sizeof(t2));

     int *x=t,*y=t2;

     for(int i=;i<m;++i) c[i]=;

     for(int i=;i<len;++i) c[x[i]=s[i]]++;

     for(int i=;i<m;++i) c[i]+=c[i-];

     for(int i=len-;i>=;--i) sa[--c[x[i]]]=i;

     for(int j=,k=;k<=len;k<<=,++j)

     {

         /*int p=0;

         for(int i=len-k;i<len;++i) y[p++]=i;

         for(int i=0;i<len;++i) if(sa[i]>=k) y[p++]=sa[i]-k;*/

         int p=;

         for(int i=;i<len;++i) q[nx[i][j]].push(i);

         for(int i=;i<len;++i)

             while(!q[sa[i]].empty())

             {

                 y[p++]=q[sa[i]].front();

                 q[sa[i]].pop();

             }

         for(int i=;i<m;++i) c[i]=;

         for(int i=;i<len;++i) c[x[y[i]]]++;

         for(int i=;i<m;++i) c[i]+=c[i-];

         for(int i=len-;i>=;--i) sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=,x[sa[]]=;

         for(int i=;i<len;++i)

             if(y[sa[i-]]==y[sa[i]]&&y[nx[sa[i-]][j]]==y[nx[sa[i]][j]]) x[sa[i]]=p-;else x[sa[i]]=p++;

         if(p>=len) break;

         m=p;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int cas=;cas<=T;++cas)

     {

         printf("Case #%d: ",cas);

         scanf("%d",&len);

         scanf("%s",s);

         for(int i=;i<len;++i) nx[i][]=(1LL*i*i+)%len;

         for(int j=;j<=;++j)

             for(int i=;i<len;++i) nx[i][j]=nx[nx[i][j-]][j-];

         getsa(''+);

         int pos=sa[len-];

         for(int i=;i<=len;++i,pos=nx[pos][]) printf("%c",s[pos]);

         printf("\n");

     }

    // for(int i=0;i<n;++i) printf("%d ",sa[i]);printf("\n");

    // for(int i=0;i<n;++i) printf("%d ",rk[i]);printf("\n");

    // for(int i=0;i<n;++i) printf("%d ",height[i]);printf("\n");

     return ;

 }