Q750: 8 Queens Chess Problem

在西洋棋得棋盤中你可以放置8個皇后而且彼此都不衝突（就是都不能吃到對方）。給你某一個皇后的位置，請你寫一個程式來輸出所有這樣可能的安排。

Input

輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列。每列有2個整數 ，代表其中一個皇后必須放置的位置。為了把棋盤標準化，我們定義棋盤最左上角的位置為（1,1）。所以下圖黑色方塊的位置為（4,6），代表第4列（ROW），第6行（COLUMN）。

Output

對每一組測試資料請先輸出表頭。然後每一種解答一列，在這裡只輸出列的位置，行的位置則以這8個數字出現的順序表示。若以Sample Output第1組測試資料為例說明：第1種解答8個皇后的位置分別為(1,1)(5,2)(8,3)(6,4)(3,5)(7,6)(2,7)(4,8)。

如果有不只一種解答，請按照字典順序由小到大排列。測試資料間亦請輸出一空白列，請參考Sample Output。

2

1 1

1 2

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      1 5 8 6 3 7 2 4
 2      1 6 8 3 7 4 2 5
 3      1 7 4 6 8 2 5 3
 4      1 7 5 8 2 4 6 3

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      3 1 7 5 8 2 4 6
 2      4 1 5 8 2 7 3 6
 3      4 1 5 8 6 3 7 2
 4      5 1 4 6 8 2 7 3
 5      5 1 8 4 2 7 3 6
 6      5 1 8 6 3 7 2 4
 7      6 1 5 2 8 3 7 4
 8      7 1 3 8 6 4 2 5