1. 


/*
Magic Square Palindrome (11221)
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2162

* Robert Reichart
* Martin Pesl
* Elvin Uzeirovic
* IF 1 C
*
* Run Time Submission Date
* 0.360 2009-04-17 13:25:50
*/

import java.io.*;

class Main{
public static void main(String... args)throws Exception{
BufferedReader is= new BufferedReader(new InputStreamReader(System.in));
final int TESTCASES =Integer.parseInt(is.readLine());
for(int z=1;z<=TESTCASES;z++){
String input = is.readLine();
StringBuilder eingabe = new StringBuilder();
for (int i=0; i<input.length();i++){
if(Character.isLowerCase(input.charAt(i))){eingabe.append(input.charAt(i));}
}

//if (z!=1){System.out.print("\n");}
double sqrt =Math.sqrt(eingabe.length());
if (sqrt%1!=0){
System.out.println("Case #" + z + ":");
System.out.println("No magic :(");
}else{
int dimension=(int)(sqrt);
char[][] array = new char[dimension][dimension];
for (int i=0; i<dimension;i++){
for (int k=0; k<dimension;k++){
array[i][k]=eingabe.charAt(i*dimension+k);
}
}

//Beginn der Tests auf MagicSquare
//Test1=Zeilenweise von oben nach unten
StringBuilder tester=new StringBuilder();
for (int i=0; i<dimension;i++){
for (int k=0; k<dimension;k++){
tester.append(array[i][k]);
}
}
if (!tester.toString().equals(eingabe.toString())){
System.out.println("Case #" + z + ":");
System.out.println("No magic :(");
continue;
}

//Test2=Zeilenweise von unten nach oben
tester.delete(0, tester.length());
for (int i=dimension-1; i>=0;i--){
for (int k=dimension-1; k>=0;k--){
tester.append(array[i][k]);
}
}
if (!tester.toString().equals(eingabe.toString())){
System.out.println("Case #" + z + ":");
System.out.println("No magic :(");
continue;
}




//Test3=Spaltenweise von links nach rechts
tester.delete(0, tester.length());
for (int i=0; i<dimension;i++){
for (int k=0; k<dimension;k++){
tester.append(array[k][i]);
}
}
if (!tester.toString().equals(eingabe.toString())){
System.out.println("Case #" + z + ":");
System.out.println("No magic :(");
continue;
}


//Test4=Spaltenweise von rechts nach links
tester.delete(0, tester.length());
for (int i=dimension-1; i>=0;i--){
for (int k=dimension-1; k>=0;k--){
tester.append(array[k][i]);
}
}
if (!tester.toString().equals(eingabe.toString())){
System.out.println("Case #" + z + ":");
System.out.println("No magic :(");
continue;
}


System.out.println("Case #" + z + ":");
System.out.println(dimension);
}
}
}
}