G. Evolutionary Tree Weights
time limit per test
4.5 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

At the Institute of Marine Biology, several new species of deep-sea mollusks have been discovered. Now, the researchers are trying to understand their genealogy. To do this, lab assistant Petya extracted a specific segment of the genome from each species of mollusk, and lab assistant Vasya constructed $$$T$$$ hypothetical partial evolutionary trees based on external characteristics.

The partial evolutionary trees constructed by Vasya are rooted trees in which each vertex corresponds to a particular species. The root corresponds to the common ancestor, and the leaves correspond to modern species.

For each species, the researchers observe the same segment of the genome which is represented as a string of characters A, G, C, and T (each character represents a nucleotide). It is known that all species have segments of the same length, but during evolution, some nucleotides may have been replaced by others (deletions and additions of nucleotides without replacement could not occur). Each of the modern species corresponds to one of $$$G$$$ segments of the genome extracted by Petya. The genome segments of the ancestor species are unknown.

From previous empirical observations, Petya and Vasya know that evolution is a slow process, and therefore, for each tree constructed by Vasya, they want to determine its minimum possible weight. The weight of an evolutionary tree is defined as the sum of the weights of its edges, and the weight of an edge is the number of nucleotides that changed between the ancestor and descendant species.

The researchers themselves could not solve such a problem, so they ask for your help!

Input

The first line contains an integer $$$G$$$ ($$$0 \le G \le 500$$$): the number of genome segments extracted by Petya.

The following $$$G$$$ lines contain these segments, one per line. The segments are given as strings of characters A, G, C, and T. It is guaranteed that the lengths of all strings are the same and do not exceed $$$500$$$.

Next, a separate line contains an integer $$$T$$$ ($$$0 \le T \le 100$$$): the number of partial evolutionary trees constructed by Vasya. Then there are $$$T$$$ descriptions of these trees.

The first line of a tree description contains two integers, $$$N$$$ and $$$M$$$ ($$$0 \le M \le N \le 500$$$): the number of vertices and leaves in the tree, respectively.

If $$$N$$$ is positive, the next $$$N - 1$$$ lines contain the parents of the vertices: the $$$i$$$-th of these lines contains the parent of vertex $$$i + 1$$$. The first vertex is the root and has no parent.

Each of the last $$$M$$$ lines of a description contain two integers, $$$v$$$ and $$$g$$$: the number of the vertex of the tree that is a leaf and the number of the corresponding genome from Petya's library. Each leaf of the tree appears in these lines exactly once. The root is considered a leaf when it is the only vertex of the tree.

Output

For each of the partial evolutionary trees constructed by Vasya, you need to output only one integer: the minimum possible weight of this tree.

Examples
Input
2
AC
TC
1
4 2
1
2
2
3 1
4 2
Output
1
Input
3
AG
GT
GC
2
5 3
1
1
2
2
3 1
4 2
5 3
3 2
1
1
2 2
3 3
Output
3
1