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