Q704: Colour Hash

有一種拼盤有兩個輪子, 而這兩個輪子都可以順時針轉和逆時針轉. 拼盤有 21 片, 10 片是有點圓的三角形, 而另外 11 片則是骨頭型. 圖1 是所要拼成的目標. 記住一個"步驟"是你必須轉動其中一個輪子往順時針或逆時針的方向直到拼盤的每一片的邊緣都能和他旁邊的那幾片的邊緣重合在一起.


圖1. 拼盤的最終目標

你的工作是寫一個程式讀入拼盤一開始的狀態並且輸出一個能夠達成目標的最短轉動序列, 我們會用底下的數字來表示每一片: 

	0 灰色(骨頭型)
	1 黃色(三角形)
	2 黃色(骨頭型)
	3 藍色(三角形)
	4 藍色(骨頭型)
	5 紫色(三角形)
	6 紫色(骨頭型)
	7 綠色(三角形)
	8 綠色(骨頭型)
	9 紅色(三角形)
	10 紅色(骨頭型)

我們可以用 24 個整數來描述一個拼盤的狀態, 前 12 個數描述左邊的輪子而後 12 個數描述右邊的輪子
我們可以把最終的目標狀態用以下這 24 個數字的序列的來表示:

0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1

而如果我們把最終的盤面的左輪往順時針方向轉一格(如圖2), 那它的狀態序列就會變成這樣:

2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1


圖2. 最終的盤面的左輪往順時針方向轉一格後的狀態

Input

第一行是一個正整數 n, 表示有幾個拼盤要處理. 接下來有 n 行每一行都有 24 個數字表示拼盤一開始的狀態

Output

對於每一組輸入你的程式都應該要輸出一行用數字描述的轉動序列, 以下是每個數字代表的意思: 

	1  左輪順時鐘轉
	2 右輪順時鐘轉
	3 左輪逆時鐘轉
	4 右輪逆時鐘轉

數字與數字之間不應該有空白存在, 如果有多個最短的轉動序列, 請輸出字典順序最小的那一個.
另外, 輸出的解答所需要的步驟數不能夠超過 16 步.

如果你沒有辦法找到一個 16 步內的解答, 請輸出"NO SOLUTION WAS FOUND IN 16 STEPS"
而如果一開始輸入的狀態就已經是所要求的最終目標的話, 請輸出"PUZZLE ALREADY SOLVED"

Sample Input

3
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 3 4 5 0 3 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 9 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 3 0 1 2 1

Sample Output

PUZZLE ALREADY SOLVED
1434332334332323
NO SOLUTION WAS FOUND IN 16 STEPS
Translated by Black Hsu