Problem2209--Magic Squares

2209: Magic Squares

Time Limit: 2 Sec  Memory Limit: 1280 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

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.

Input

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.

Output

For each test case, print the minimal number of steps needed. If the task is impossible, print -1.

Sample Input Copy

4
135876492
438975261
672159834
129764583

Sample Output Copy

2
1
0
4