八皇后

題目敘述

會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。

我們現在要算的是n皇后，對於某個滿足要求的n皇后的擺放方法，定義一個皇后串$a$與之對應，即$a=b_1 \; b_2 \; … \; b_n$，其中$b_i$為相應擺法中第$i$行皇后所處的列數。已經知道8皇后問題一共有92組解（即92個不同的皇后串）。

現在給你數字n，請將n皇后的所有解，以皇后串按字典序的方式輸出，不知道甚麼是字典序的就上網查一下吧，做為比賽選手這是一定要知道的

輸入說明

輸入有多行，每行一個數字n,\(1 \leq\)n\(\leq 14\)，表示詢問為n皇后問題

輸出說明

先輸出這是第幾筆測資，接著按字典序輸出n皇后的解，在輸出有幾組解

詳請見範例輸入輸出

範例輸入

3
4
6

範例輸出

case 1:
0
case 2:
2 4 1 3
3 1 4 2
2
case 3:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
4

配分方法

• 20% 範例測資
• 30% N\(\leq 8\)
• 50% N\(\leq 14\)

Hints

備註

Judge Setting