We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #209: Circular Logic

Project Euler #209: Circular Logic

This problem is a programming version of Problem 209 from projecteuler.net

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:

image

How many -input binary truth tables, , satisfy the formula for all -bit inputs ?

Input Format

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:

a1&a2+a1+1

One should interprete this as the function

Constraints

  • Every description of a function has length . Moreover, every possible summand occurs in each description not more than once.

Output Format

Print exactly one number, which is the answer to the problem.

Sample Input 0

1
1
a1
a1+1

Sample Output 0

3

Explanation 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

1
1
a1
0

Sample Output 1

2

Explanation 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 :

  • . After substitution we get which is always true.
  • . Now we get . It is wrong for .

That leaves us with only two good .

Sample Input 2

2
2
a1&a2
a1&a2+1
a1
a1&a2+1
2
1
a1
a1&a2+a2+a1+1
a2+a1

Sample Output 2

4
5

Sample Input 3

2
3
a2&a3+a1&a3+a1
a1&a2&a3+a2&a3+a2
a2&a3+a3+a2
a1&a2&a3+a1&a3
a2&a3+a1&a3+a1&a2+a2
a2&a3+a1&a3+a3+a1&a2+a1
3
a1&a2&a3+a2&a3+a3+a2+a1
a1&a2&a3+a2&a3+a1&a2+1
a1&a2&a3+a2&a3+a1&a3+a1&a2+a1
a1&a2&a3+a2&a3+a3+a1&a2+a2+a1+1
a1&a2&a3+a2&a3+a3+a1&a2+a2+a1
a1&a2&a3+a1&a3+a1&a2+a2+a1+1

Sample Output 3

48
80