Problem Description
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:
(a11 . x1) ^ (a12 . x2) ^ … ^ (a1m . xm) = 0
(a21 . x1) ^ (a22 . x2) ^ … ^ (a2m . xm) = 0
…
(an1 . x1) ^ (an2 . x2) ^ … ^ (anm . xm) = 0
which satisfies the following conditions:
1. aij in {0,1} for 1 ≤ i ≤ n and 1 ≤ j ≤ m;
2. xi in Si where Si is a subset of {0,1,2,3}, 1 ≤ i ≤ m;
3. |Si| ≤ 3, 1 ≤ i ≤ m;
4. 1≤n ≤ 30, 1 ≤ m ≤ 22.
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 T (<= 15) indicating the number of test cases, then T 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 aij. The next m lines are descriptions of Si that the leading integer K denotes the number of elements in Si 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.
Sample Input
1
1 2
1 1
3 0 1 2
2 3 1
Sample Output
1
