I guess the n-queen problem is known by every person who has studied backtracking. In this problem you should count the num- ber of placement of n queens on an n ∗ n board so that no two queens attack each other. To make the problem a little bit harder (easier?), there are some bad squares where queens cannot be placed. Please keep in mind that bad squares cannot be used to block queens’ attack. Even if two solutions become the same after some rotations and reflections, they are regarded as different. So there are ex- actly 92 solutions to the traditional 8-queen problem. Input The input consists of at most 10 test cases. Each case contains one integers n (3 ≤ n ≤ 15) in the first line. The following n lines represent the board, where empty squares are represented by dots ‘.’, bad squares are represented by asterisks ‘’. The last case is followed by a single zero, which should not be processed. Output For each test case, print the case number and the number of solutions. Sample Input 8 ........ ........ ........ ........ ........ ........ ........ ........ 4 ... .... .... .... 0 Sample Output Case 1: 92 Case 2: 1