題目描述
相信 N-Queens 問題對每個研究 backtracking 的人來講都不陌生，這個問題是要在一個 $N \times N$ 大小的棋盤上擺 $N$ 個皇后，讓她們不會互相攻擊到。為了讓這個問題更難一點，我們設計了一些障礙物在棋盤上，在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。
在傳統的 8-Queen 問題中，旋轉與鏡射被視為不同解法，因此我們有 92 種可能的方式來放置皇后。
輸入格式
輸入的資料最多包含 10 筆測試個案，每個測試個案的第一行會有一個整數 $N$ ($3 \lt N \lt 20$)，接下來的 $N$ 行代表棋盤資料，點號 '.' 代表空的盤格，星號 '*' 代表放有障礙物的盤格。
輸出格式
對每筆測試個案，輸出這是第幾個 case 以及這個 case 有幾種可能的放置方式。
範例輸入
8................................................................4.*..............
範例輸出
Case 1: 92Case 2: 1
備註
- 2016/02/29 增加強迫平行的測試資料。