Recently, Jimmy is learning about linear algebra from Blue Mary while having the course of Boolean algebra in class offered by Prof. Z. Since Jimmy has been thoroughly bored by the boring homework assigned by two teachers, evil Jimmy plans to set a hard question to baffle them as revenge for their heavy tasks. As a result, Jimmy comes up with an idea that merging the knowledge from both the two classes and constructs a complicate problem: the XOR equation system.

Let's consider the following equations:

which satisfies the following conditions:

In the system of equations, operation . denotes the multiplication operation while ^ is for bitwise XOR. Moreover, the bitwise XOR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same.

Rather than expecting a solution of a specified equation system, Jimmy would like to ask the teachers to calculate that how many distinct solutions can satisfy a given equation system. What a confusing puzzle! Help Jimmy's teachers please!

Input

There are several test cases. The first line of input is a single positive integer (<= 15) indicating the number of test cases, the test cases follow.

For each test case, the first line contains two integers N and M giving the two dimensions of the equation system respectively where N is the number of rows and M for columns. Then N lines are following, each line contains M integers. Item at line i and column j represents a_ij. The next M lines are descriptions of S_i that the leading integer K denotes the number of elements in S_i and the following K integers represent elements.

Output

For each test case, output one line containing a single integer which represents the answer of this case.

Example

Input:
1
1 2
1 1
3 0 1 2
2 3 1
Output:
1