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.

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.

提交代码