Time Limit: 10 Seconds
Memory Limit: 32768 KB
Dice Matrix is a puzzle made of several dice. The rules of this puzzle are as follows.
- Dice with six faces as shown in following figure are used in the puzzle.
- The direction of each die is also shown as in the following figure initially.
- The dice are arranged in n rows and m columns.
The following figure shows a 3 * 3 dice matrix.
- Each time you can select a row or a column to rotate.
- You can rotate any angle you like.
- All the dice in that row/column must be rotated the same angle in the same direction.
- The dice can only be rotated perpendicular to the row/column. You can't rotate the dice along the row/column. (You can see the sample for more details.)
Given the target top faces of a dice matrix, your task is to find the minimum steps from the initial configuration to the target one.
Standard input will contain multiple test cases.
The first line of the input is a single integer T (1 <= T <= 2000) which is the number of test cases.
And it will be followed by T consecutive test cases.
The first line of each test case contains two integers n and m (1 <= n, m <=4, n * m <= 10), indicating the number of rows and the number of columns of the dice matrix.
The next n lines will contain m integers separated by one space each, which are between 1 and 6 inclusive, indicating the target top faces of the dice matrix.
If you can make it to the target result in 5 steps, print the number of minimum steps in one line; otherwise print the word "Impossible" on a single line.
In the first sample, you can get the result by rotating the first column by 90 degrees clockwise.
In the second sample, you can get the result by rotating the first column by 180 degrees clockwise.
In the third sample, you can not select the first row and rotate each dice along the row. You can only rotate each column separated.
In the fourth sample, no rotation is needed.
Author: GUAN, Yao
Source: Zhejiang University Local Contest 2008