Problem Description

Ken is learning the Trie. He learned that Trie is a rooted tree to store some strings. There is a character on each edge of a Trie. He uses $S(i)$ to denote the string concatenated by the characters on the path from the root to node $i$.

Now he needs to deal with two kinds of operations:

$\qquad \cdot$ attach: attach a new mark(different from any marks that already exist) to a set of Trie nodes once at a time. Note that one node may be attached to multiple marks.

$\qquad \cdot$ query: ask for how many mark properties a certain node matches. We say a node matches a mark property if and only if there exists a node $j$ that has the corresponding mark and $S(j)$ is a suffix of $S(i)$. Different marks corresponds to different mark properties.

Please help him handle these queries.

Input

The first line contains a single integer $T$ ($1 \le T \le 5$), indicating the number of test cases. Then $T$ test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$,$\sum n \le 2\times 10^6$), indicating the number of Trie nodes.

Lines through the second to the $n$-th ($n-1$ lines in total) describe Ken's Trie. The $i$-th line contains an integer $u$ $(1 \le u < i)$ and a lowercase latin letter $c$, which means that the father of node $i$ is node $u$ and the character on that edge is $c$. It is guaranteed that for each node, letters on edges connecting the node and its children are distinct.

The next line contains a single integer $m$ $(1 \le m \le 10^5,\sum m \le 2\times 10^6)$, indicating the number of operations.

The next $m$ lines describe all the operations. Each line describle one operation, and it is formatted in one of the two following formats, depends on the kind of it:

$\qquad \cdot$ "$1\ k\ x_{1}\ x_2\ \ldots \ x_k$'' - attach a new mark to the node set $\{x_1, x_2, \ldots, x_k\}$, where all the $x_i$ are distinct.

$\qquad \cdot$ "$2\ x$'' - query for how many mark properties node $x$ can match.

Output

For each test case, output the answer for each query operation, one answer in a line.

1
6
1 a
1 b
1 c
3 a
3 b
7
1 2 2 3
2 5
1 2 3 4
2 6
2 1
1 2 1 2
2 6

1
2
0
3