Anna University Local Contest #11

You and your friends are playing Game of Iron Thrones. When you play the Game of Iron Thrones, you roll n biased dice together. You know how biased the dice are on each face.

Find the probability that you will get at least K 6's.

Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers n - the number of dice and K - as defined above. The next n lines consists of 6 decimal numbers denoting the probability of getting the corresponding face. (Face 1 to 6)

Output:

For each test case, find the probability to get at least K 6's when you roll all the n dice at once. Your solution's absolute or relative error must be strictly less than 10^-2. (i.e. your solution can make mistakes upto 0.01)

Constraints

1 <= t <= 100

1 <= n <= 1000

1 <= K <= 1000

Example

Input:
4
6 6
0 0 0 0 0 1
0 0 0 0 0.5 0.5
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0.5 0 0.5
0 0 0 0 0 1
3 1
0.2 0.2 0.2 0.2 0.2 0
0.2 0.2 0.2 0.2 0.2 0
0 0 0 0 0 1
3 2
0.2 0.2 0.2 0.2 0.2 0
0.2 0.2 0.2 0.2 0.2 0 
0 0 0 0 0 1
2 1
0.2 0.2 0.2 0.2 0 0.2
0 0 0 0.5 0.25 0.25

Output:
0.25
1
0
0.4

Explanation

Case 1: There are 6 dice and we need at least 6 sixes. The probability to get 6 in all dice = 1*0.5*1*1*0.5*1 = 0.25.

Case 2: There are 3 dice and we need exactly one 6. No matter how many times you throw the dice, you will always get at least one 6.

Case 3: There are 3 dice and we need at least two 6s. For the given biased dice in which two of them never turns 6 the probability will be 0.

Case 4: Note that there can be more than K 6's. The probability in this case would be 0.2*0.25 + 0.2 * (1-0.25) + (1-0.2) * 0.25 = 0.4.

Note: Avoid COUT for this problem as it will print the result in scientific notation.