//hdu6223  249ms

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<string.h>

 #include<sstream>

 #include<set>

 #include<map>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<bitset>

 #define CLR(a,b) memset(a,b,sizeof(a))

 using namespace std;

 typedef long long ll;

 inline int rd() {

     int f=;

     int x=;

     char s=getchar();

     while(s<''||s>'') {

         if(s=='-')f=-;

         s=getchar();

     }

     while(s>=''&&s<='') {

         x=x*+s-'';

         s=getchar();

     }

     x*=f;

     return x;

 }

 const int inf=0x3f3f3f3f;

 const int maxn=;

 int maxx,vis[maxn],tot;

 char a[maxn],ans[maxn];

 ll n;

 struct dian {

     int step;//步数

     ll pos;//在原数组中对应的位置

     dian() {}

     dian(int step,ll pos):step(step),pos(pos) {}

 };

 queue<dian >q;

 inline void bfs() {

     dian s;

     while(!q.empty()) {

         s=q.front();

         q.pop();

         if(s.step==n) {//终止条件

             continue;

         }

         if(a[s.pos]==ans[s.step]) {//如果相等，则代表目前的状态是最优的

             if(vis[s.pos]==s.step)continue;//之前已经来到过这个状态

             vis[s.pos]=s.step;

             s.pos= (s.pos * s.pos + ) % n;

             s.step++;

             if(a[s.pos]>=ans[s.step]) {

                 ans[s.step]=a[s.pos];

                 q.push(s);

             }

         }

     }

 }

 int main() {

     int T;

     int cas=;

     cin>>T;

     while(T--) {

         while(!q.empty())q.pop();

         tot=;

         scanf("%lld",&n);

         maxx=;

         scanf("%s",a);

         for(int i=; i<n; i++) {

             maxx=max(maxx,(int)a[i]);

         }

         for(int i=; i<n; i++) {

             if(a[i]==maxx) {

                 q.push(dian(,i));//最大值入队

             }

         }

         CLR(ans,-);

         CLR(vis,-);

         ans[]=maxx;//第一个位置先更新

         bfs();//主要过程

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

         ans[n+]='\0';

             printf("%s",ans+);

         printf("\n");

     }

 }