A magic square is an n*n arrangement of numbers 1,2,..... n2, such that the sum of numbers in each
row, column, and main diagonal is the same. There are exactly two main diagonals in a square.
Given a 3*3 square of digits 1 to 9, your task is to ¯nd the minimal steps needed to transform it to a
magic square. Each step is rotating any of the four 2*2 sub-square in the corners, either clockwise or
counter-clockwise, 90 degrees.
The first line contains t (<= t<=25), the number of test cases followed. Each test case is a string
containing exactly 9 characters. The string is guaranteed to be a permutation of nine digits 1,2,....... 9.
For each test case, print the minimal number of steps needed. If the task is impossible, print -1.
4 135876492 438975261 672159834 129764583
2 1 0 4