A magic square palindrome is a sentence whose characters can be divided in a K × K square table with the property that the original sentence can be read from the table in four different ways: • Start from the (1,1) cell, move right until the end of the line and than proceed to the next line. • Start from the (1,1) cell, move down until the end of the column and then proceed to the next column. • Start from the (K,K) cell, move left until the beginning of the line and then proceed to the previous line. • Start from the (K,K) cell, move up until the beginning of the column and then proceed to the previous column. “Sator arepo tenet opera rotas” is probably the most famous magic square palindrome. We can arrange it in a K = 5 (5 × 5) table in the following way: sator arepo tenet opera rotas Notice that the original sentence can be read from the table in the four different ways described above. Input The first line of input gives the number of cases, T (1 ≤ T ≤ 60). T test cases follow. Each one contains one line L, such that 0 < length(L) < 10.000, with the sentence (that can contain characters [a-z], whitespace, comma, period, interrogation and exclamation points and parentheses). Please notice that the magic square palindrome table ignores all whitespace and punctuation symbols. Output The output is comprised of two lines for each input data set. The first line identifies the data set with a number (starting from one and incrementing at each new data set). The second line gives the dimension of the magic square palindrome table (the K value described above) or the expression ‘No magic :(’ if the sentence is not a magic square palindrome. Sample Input 3 sator arepo tenet opera rotas this sentence is, quite clearly, not a magic square palindrome! but then again, you never know... muse sun, eve.s e(y)es even use sum.
2/2 Sample Output Case #1: 5 Case #2: No magic :( Case #3: 5