006 - フロッピーキューブ

問題

フロッピーキューブをプログラミングで解いてみましょう。フロッピーキューブは図のように表面に色のついた９個の立方体から構成されている立体パズルで、キューブの列を回転させることによって、６つの各面の色をそろえます。

フロッピーキューブに対しては下図のような４種類の操作を行うことができ、一回の操作で、端にある３つの隣接したキューブを１８０度回転することができます。わかりやすいように、図では、上面に＋(赤色)、下面に＊(緑色)、右前面に□(黄色)、左前面に●(青色)、右奥面に○(水色)、左奥面に■紫色) の記号が付いている状態を初期状態としています。

フロッピーキューブの初期状態が与えられるので、パズルを解くために必要な最小の操作回数を求めるプログラムを作成してください。

入力

入力は以下の形式で与えられる。

N
puzzle1
puzzle2
:
puzzleN

１行目のN (1 ≤ N ≤ 30) は操作回数を計算したいパズルの数である。続くN行に各フロッピーキューブの初期状態 puzzle_i が与えられる。puzzle_i は以下の形式で与えられる。

p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p23 p24 p25 p26 p27 p28 p29 p30 

各フロッピーキューブの情報は 30 個の整数 p_i (1 ≤ p_i ≤ 6) からなる。p_i は、下図のようにフロッピーキューブの各面に番号 i を振ったときの、そのキューブの面の色を表す。

パズルは、多くとも８回の操作で解くことができると仮定してよい。

出力

パズルごとに、最小の操作回数を１行に出力する。

入出力例

入力例

4
1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3
3 3 3 1 1 1 1 1 1 2 2 2 4 4 6 4 6 6 5 5 5 3 3 3 3 3 3 1 1 1
3 3 3 1 1 3 1 1 1 2 2 5 6 4 4 4 6 6 2 5 5 3 3 3 1 3 3 1 1 1
1 3 1 3 1 3 3 1 3 2 2 2 6 4 4 6 6 4 5 5 5 1 3 1 1 3 1 3 1 3

出力例

0
1
2
7