Chessboard Game

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

LJB likes playing chessboard game.Now there are some chesses in the square chessboard. LJB has m chesses at his hands.He wants to put all of them on the chessboard at random .We can not put a chess on a position which already contains a chess. After putting all of them,he will be happy if an entire row, column or diagonal consists of chess.So I want you to calculate the percentage he will be happy.

Input

The first line contains an integer t ( 1 <= t <= 100 ): the number of test cases. Then for each test case:The first line contains two integers n ( 1 <= n <= 8 ) and m ( 0 =< m <= 64),where n is the size of the square chessboard and m is the number of chesses at LJB's hand. Next n lines each contains exactly n characters. Each character will be either '*' or '.', representing a chess on the position or an empty position.There will be at least m empty positions on the board, and there is no any row, column or diagonal all covered by chess yet.

Output

For each test case, output the result in the form of sample.You should print the case number and the percentage LJB will be happy.Your answer is supposed to be rounded to six decimal digits.

Sample Input

1
7 10
*.*.***
.**.**.
***.*..
******.
.*.....
....*.*
...**.*


Sample Output

Case 1: 85.232524%




Hint

None

Source

陶翔专场练习赛

提交代码