#include<bits/stdc++.h>

 #define LL long long

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define piii pair<int, pair<int,int>>

 using namespace std;

 const int N=2e5+;

 const int M=1e4+;

 const int inf=0x3f3f3f3f;

 const LL INF=0x3f3f3f3f3f3f3f3f;

 const int mod=1e9 + ;

 int n, tot, a[N], nx[N][], sa[N], t[N], t2[N], c[N], nxk[N], ans[N];

 vector<int> prek[N];

 void buildSa(int n, int m) {

     int i, j, *x = t, *y = t2;

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

     for(i = ; i < n; i++) c[x[i] = a[i]]++, nxk[i] = i;

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

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

     for(int k = ; k <= n; k <<= ) {

         for(i = ; i < n; i++) nxk[i] = nx[nxk[i]][], prek[i].clear();

         for(i = ; i < n; i++) prek[nxk[i]].push_back(i);

         int p = ;

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

             for(j = ; j < prek[sa[i]].size(); j++)

                 y[p++] = prek[sa[i]][j];

         }

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

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

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

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

         swap(x, y);

         p = ; x[sa[]] = ;

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

             if(y[sa[i - ]] == y[sa[i]] && y[nxk[sa[i - ]]] == y[nxk[sa[i]]])

                     x[sa[i]] = p - ;

             else x[sa[i]] = p++;

         }

         if(p >= n) break;

         m = p;

     }

 }

 int main() {

     int T; scanf("%d", &T);

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

         scanf("%d", &n);

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

             scanf("%1d", &a[i]);

         }

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

             nx[i][] =  (1ll * i * i + ) % n;

         }

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

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

                 nx[i][j] = nx[nx[i][j - ]][j - ];

             }

         }

         buildSa(n, );

         tot = ;

         int now = sa[n - ];

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

             ans[tot++] = a[now];

             now = nx[now][];

         }

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

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

             printf("%d", ans[i]);

         puts("");

     }

     return ;

 }

 /*

 */