No submission language available for this problem.

Description

Input

The first line contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the number of songs in the album.

Each of the next $n$ lines contains the desciption of the $i$-th song of the album in the following format:

• $1~c$ — $s_i$ is a single lowercase Latin letter;
• $2~j~c$ — $s_i$ is the name $s_j$ ($1 \le j < i$) with a single lowercase Latin letter appended to its end.

The next line contains a single integer $m$ ($1 \le m \le 4 \cdot 10^5$) — the number of Vova's questions.

Each of the next $m$ lines contains the desciption of the $j$-th Vova's question in the following format:

• $i~t$ ($1 \le i \le n$, $1 \le |t| \le 4 \cdot 10^5$) — count the number of occurrences of string $t$ in $s_i$ (the name of the $i$-th song of the album) as a continuous substring, $t$ consists only of lowercase Latin letters.

It's guaranteed that the total length of question strings $t$ doesn't exceed $4 \cdot 10^5$.

Output

For each question print a single integer — the number of occurrences of the question string $t$ in the name of the $i$-th song of the album as a continuous substring.

Samples

20
1 d
2 1 a
2 2 d
2 3 a
2 4 d
2 5 a
2 6 d
2 7 a
1 d
2 9 o
2 10 k
2 11 i
2 12 d
2 13 o
2 14 k
2 15 i
2 1 o
2 17 k
2 18 i
2 15 i
12
8 da
8 dada
8 ada
6 dada
3 dada
19 doki
19 ok
16 doki
15 doki
9 d
1 a
20 doki

4
3
3
2
0
1
1
2
1
1
0
2

Note

Song names of the first example:

1. d
2. da
3. dad
4. dada
5. dadad
6. dadada
7. dadadad
8. dadadada
9. d
10. do
11. dok
12. doki
13. dokid
14. dokido
15. dokidok
16. dokidoki
17. do
18. dok
19. doki
20. dokidoki

Thus the occurrences for each question string are:

1. string "da" starts in positions $[1, 3, 5, 7]$ in the name "dadadada";
2. string "dada" starts in positions $[1, 3, 5]$ in the name "dadadada";
3. string "ada" starts in positions $[2, 4, 6]$ in the name "dadadada";
4. string "dada" starts in positions $[1, 3]$ in the name "dadada";
5. no occurrences of string "dada" in the name "dad";
6. string "doki" starts in position $[1]$ in the name "doki";
7. string "ok" starts in position $[2]$ in the name "doki";
8. string "doki" starts in positions $[1, 5]$ in the name "dokidoki";
9. string "doki" starts in position $[1]$ in the name "dokidok";
10. string "d" starts in position $[1]$ in the name "d";
11. no occurrences of string "a" in the name "d";
12. string "doki" starts in positions $[1, 5]$ in the name "dokidoki".