You are given a N x N grid, where each cell in the grid is either blocked or free. You can place any number between 1 to N in the free cells. You are required to assign numbers to the free cells. No free cells should be left empty after the assignment, i.e. each free cell must contain exactly one number from the range [1-N].

You are also given a target value V. Find out how many ways we can assign numbers to the free cells such that their sum equals V. It is also required to satisfy the following constraints:

1. For any row, all the numbers present in that row should be distinct.
2. For any column, all the numbers present in that column should be distinct.

Two ways are considered different if any particular cell has different values assigned.

Let M denote the total number of free cells. It is guaranteed that there will be at least 1 and no more than 12 free cells.

Input

The first line contains an integer T, denoting the number of test cases. The next line contains two integers, N and V. The next N lines contains the grid, each line contains the corresponding row of the grid.

Cells marked with a '.' indicates free cells, and cells marked as 'X' denotes blocked cells. Each cell can be either blocked or free so the grid will not contain any other extra characters.

Constraints

1 < T ≤ 120

1 < N ≤ 12

1 < V ≤ 144

1 < M ≤ 12

For 60% of the test cases, the following constraints will hold:

1 < N ≤ 8

1 < M ≤ 8

Output

For each test case, output the case number followed by the number of ways to create the assignment. Please check the sample input/output for more clarity.

Example

Input:
5
1 1
.
2 2
.X
.X
2 3
.X
X.
3 7
.X.
X.X
XX.
5 15
XX.XX
XX.XX
.XXX.
XX.XX
XX.XX

Output:
Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 9
Case 5: 192