A -input binary truth table is a map from input bits (binary digits,  or ) to output bit. For example, the -input binary truth tables for the logical and functions are:
How many -input binary truth tables, , satisfy the formula
for all -bit inputs ?
The first line of each test file contains a single integer that is the number of queries per test file. blocks follow. On the first line of each block there is a single integer . lines follow with the descriptions of the functions on each line. lines follow then with the descriptions of the functions on each line.
Every description follow the grammar described below:
where means logical , means logical , result into .
For example, one of the possible function descriptions could look as follows:
One should interprete this as the function
Every description of a function has length . Moreover, every possible summand occurs in each description not more than once.
Print exactly one number, which is the answer to the problem.
Sample Input 0
Sample Output 0
Let's look at all possible :
. Then it doesn't depend on and the statement is always true
. It also doesn't depend on but now the statement is always false
and both lead us to the statement which is always true.
That said, our answer is .
Sample Input 1
Sample Output 1
Using the same logic as in previous sample, we can deduce that is good and is bad. Let's take a look into and :