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


int main()
{
    int t;

    scanf("%d ",&t);

    char l[10001], matriz[101][101];;

    for(int i=0;i<t;i++)
    {
        int j=0;

        while(scanf("%c",&l[j])==1 && l[j]!='\n')
        {
            if(l[j]<'a' || l[j]>'z') j--;
            j++;
        }


        l[j] = '\0';


        double tamlinha;

        tamlinha = sqrt(strlen(l));

        if((int)tamlinha*(int)tamlinha!=strlen(l)) printf("No magic :(\n");
        else
        {
            int w=0;

            for (int j = 0; j < (int) tamlinha; ++j)
            {
                for (int k = 0; k < (int) tamlinha; ++k)
                {
                    matriz[j][k] = l[w];
                    w++;
                }
            }

            printf("Case #%d:\n",(i+1));

            int ver=0;

            for(int j=0;j<(int) tamlinha;j++)
            {
                for (int k=0;k<(int)tamlinha;k++)
                {
                    if(matriz[j][k]!=matriz[k][j] || matriz[j][k]!=matriz[(((int)tamlinha)-1)-j][(((int)tamlinha)-1)-k] || matriz[j][k]!=matriz[(((int)tamlinha)-1)-k][(((int)tamlinha)-1)-j])
                    {
                        ver =1;
                        break;
                    }
                }
                if(ver==1) break;
            }

            if(ver==0) printf("%d\n",(int) tamlinha);
            else printf("No magic :(\n");
        }



    }

    return 0;


}