- All Contests
- ProjectEuler+
- Project Euler #209: Circular Logic

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

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
```