F、Squirtle

Squirtle has a binary expression tree which is rooted at node 1.

There are n leaves on the tree, each leaf of which contains a binary number that can be either 0 or 1, and each non-leaf node contains a binary logical operator.

There are 16 types of binary logical operator in total. Here we use an integer from 0 to 15 to represent a binary logical operator. Suppose that an integer i's binary expression is , then it represents where f_i(0,0)=i₀,f_i(0,1)=i₁,f_i(1,0)=i₂,f_i(1,1)=i₃. The first parameter corresponds to the left operand and vice versa. For example, the bitwise-and operator is represented by 8.

Squirtle can fill non-leaf node i with a binary logical operator in set S_i.

Given the tree and all the sets, Squirtle wants to know how to fill non-leaf nodes so that the sum of the results of all the expressions, where the leaves take all the possible values, is maximum.

The input starts with one line containing exactly one integer t which is the number of test cases. (1 ≤ t ≤ 20)

For each test case, the first line contains exactly one integer n which is the number of leaf nodes. (2 ≤ n ≤ 2000)

Each of the next n-1 lines contains a string si of length 16. It is guaranteed that si only consists of 0 and 1 and contains at least one 1. If si's j-th character(numbered from 0) sij=1, then operator j∈ Si, otherwise operator .

Each of the next 2n-2 lines contains an integer ai, which represents the father of i+1. It is guaranteed that the tree is valid. That is, the tree is a binary tree whose nodes have either 0 or 2 children. Nodes from 1 to n-1 are guaranteed to be non-leaf nodes. The child with the smaller index is regarded as the left operand. (1 ≤ ai ≤ i)

For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the maximum possible sum.

2
2
0000000010000010
1
1
3
0000000010000010
0000000010000011
1
1
2
2

Case #1: 3
Case #2: 8