[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2014 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ] 

A question we may ask ourselves if we have a lot of free time (or if we are mathematicians, which is practically the same thing) is the following: given a board of N × N square cells, in how many ways can we cover it with dominoes so that the pieces do not overlap and there are no cells left uncovered? Dominoes are rectangles composed of two adjacent square cells, and can be either horizontal (1 × 2) or vertical (2 × 1). For example, there are only two ways to cover a 2 × 2 board, but there are 12,988,816 ways to cover an 8 × 8 board.

Figure 1: (a) The two ways to cover a 2 × 2 board with horizontal dominoes (left) and vertical dominoes (right); (b) a possible covering of an 8 × 8 board.

For those with even more free time, there is a variant of this question in which we consider a board with some of its cells occupied, so that we should count the number of coverings in which the domino pieces cover only the unoccupied cells without overlapping or leaving holes. For example, there are two ways to cover a 3 × 3 board in which the central cell is occupied, and 75,272 ways to do so in a 7 × 7 board.

In this problem we will turn our attention to a variant of this variant of the original question, specifically thought for those of you with too much free time. We will again consider an N × N board in which some cells can be occupied, but we now want to cover it using fractal dominoes of order K.

Figure 2: (a) A 4 × 4 board with two occupied cells; (b) one of the 89 horizontal dominoes of order one for this board; (c) one of the 52 vertical dominoes of order one for the same board; (d) a covering of the board in (a) with the fractal dominoes of order one in (b) and (c).

Given an N × N board, a fractal domino of order K = 0 is a regular domino piece, i.e. a rectangle of 1 × 2 or 2 × 1 cells. A fractal domino piece of order K > 0 consists of a regular domino in which each cell is a copy of the given N × N board, and the piece as a whole is covered by fractal dominoes of order K-1.

Note that in general for K > 1 there can be more than one fractal domino piece of order K-1 of each type (horizontal or vertical). In this case, we assume that when using a domino piece it is chosen with uniform probability among all possible fractal domino pieces of the same type and order. In a similar fashion, if there is more than one possible covering for a given board or fractal domino, we will assume all of them are equally probable.

When covering a board with fractal dominoes of order K one will use a certain amount of pieces of order K, a larger amount of pieces of order K-1, an even larger amount of pieces of order K-2, and so on. This will go on up to the point where one uses a possibly huge amount of pieces of order zero, i.e. regular domino pieces with nothing inside. For example, in Figure 2d the board is covered with seven fractal dominoes of order one and 98 fractal dominoes of order zero.

The task in this problem is to calculate the expected proportion of fractal dominoes of order zero (i.e. regular pieces) that are vertical, if we assume that all coverings of a given board with fractal dominoes of a given order K are equally probable.

Input

The first line contains an integer number T, the number of test cases (1 ≤ T ≤ 200). T test cases follow.

The first line of each test case contains two integers N and K, representing the size of the board and the order of the fractal dominoes that we want to use to cover it, respectively (2 ≤ N ≤ 8 and 0 ≤ K ≤ 10⁹). The following N lines contain N numbers each, being the j-th number in the i-th line a 1 if the cell in row i and column j of the board is occupied, and 0 otherwise. The given board is not completely occupied, and it is always possible to cover it using dominoes.

Output

For each test case, print a single line containing a rational number representing the expected proportion of fractal dominoes of order zero that are vertical, when we consider that all coverings of the given board with fractal dominoes of order K are equally probable. Print the result using exactly 5 decimal digits after the decimal point, rounding if necessary.

Example

Input:
1
1
4 2
0 0 0 0
0 1 1 0
0 0 0 0
0 0 0 0

Output:
0.50750