Time Limit: 2000 MS    Memory Limit: 65536 K 


Description

There are N equations: A00*X0 + A01*X1 + A02*X2 + ... + A0M-1*XM-1 = B0 A10*X0 + A11*X1 + A12*X2 + ... + A1M-1*XM-1 = B1 A20*X0 + A21*X1 + A22*X2 + ... + A2M-1*XM-1 = B2 ...... AN-10*X0 + AN-11*X1 + AN-12*X2 + ... + AN-1M-1*XM-1 = BN-1 All the operation is module 2. All the X is 0 or 1. How many solutions for the N equations?

Input

The first line of input is the number of test case. For each test case: The first line contains two integers N and M. The next N lines each contains M+1 integers, Aij and Bi. There is a blank line before each test case. 1 <= N,M <= 15 0 <= Aij,Bi <= 1

Output

For each test case output the answer on a single line.

Sample Input

3 3 4 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 4 3 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 4 3 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1

Sample Output

2 0 1

Source

8th SCUPC

Author

windy7926778