Submit: 1 Solved: 1

[Submit] [Status] [Web Board] [Creator:]

A magic square is an n*n arrangement of numbers 1,2,..... n^{2}, 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
```