Hello From Linear Algebra

Techboy has m equations with n unknowns like below –

ai1 x1+ ai2 x2+⋯⋯⋯⋯⋯+ ain xn= di , where 1≤i≤m

Techboy finds an answer. Now Techboy wants Asuna to set valid values for n unknowns of each equation if possible. What is the probability that Techboy’s solution and Asuna’s solution for m equations are exactly same? Assume that both solutions are correct.

Input

At first, you are given an integer T (T<=100), which is the number of test cases. For each case, you will be given two positive integers m & n that are the number of equations and number of unknowns in that equation (1 <= m, n <= 100). Then there will be m lines each containing n+1 numbers. First n numbers are the ai1,ai2 ⋯⋯⋯⋯ain and the (n+1)th number is the d for that particular equation. (0 <= |aij| , |d| <= 100)

Output

You have to print the probability that is mentioned in the description part for every test case in a new line. Errors less than 10-6 will be ignored

Sample

Input	Output
1 2 2 1 1 4 1 -1 2	1