Left Mouse Button#1092

Left Mouse Button

1 second

64 megabytes

Easy

Mine sweeper is a popular game in the Windows operating system. The objective of the game is to locate the mines and mark their positions. You can place a flag on a cell where you think there is a mine using the right mouse button. To open a cell you believe does not contain a mine, you use the left mouse button. If the opened cell contains a mine, it explodes and you lose. Otherwise, there are two possible cases.

In the first case, a number from $1$ to $8$ appears on the square, indicating the number of mines adjacent to this cell. For example, if after clicking the left mouse button you see the number $8$ in a square, it means all $8$ neighboring cells contain mines.

In the second case, if there are no mines in any adjacent cells, not only is this cell opened, but all adjacent cells are opened as well. If some of these adjacent cells also have no neighboring mines, their neighbors are opened recursively. The computer assists you by revealing all contiguous mine-free cells in this process.

The goal is to open all mine-free cells.

Tom enjoys this game, but unfortunately his right mouse button is broken, so he can only use the left mouse button. To avoid further damaging his mouse, he wants to finish the game using the minimum possible number of left clicks. Given the initial state of the game, determine the minimum number of left mouse button clicks required.

Input

The first line contains an integer $T$ ( $T \leq 12$ T \leq 12), the number of test cases.

Each test case starts with a line containing an integer $n$ ( $5 \leq n \leq 9$ 5 \leq n \leq 9), the size of the minefield.

Each of the next $n$ lines contains $n$ characters $M_{ij}$ M_{ij} ( $1 \leq i, j \leq n$ 1 \leq i, j \leq n), where $M_{ij}$ M_{ij} indicates the status of the cell at row $i$ and column $j$ : - ' $@$ ' denotes a mine. - ' $0$ ' to ' $8$ ' denote the number of mines adjacent to the cell. ' $0$ ' indicates there are no adjacent mines.

All positions are guaranteed to be valid.

Output

For each test case, print a line containing the test case number (starting from $1$ ), followed by the minimum number of left mouse clicks required (see example output).

Examples

Example


Case 1: 7
Case 2: 2

Example 1