Royal Names Prefix Query

In the Royal Family, names are very important! The founder of the Royal Family has a single uppercase letter as her name. Each subsequent Royal Lady's name is formed by concatenating an uppercase letter and her mother's name. For example, if a lady's mother's name is \( M \) and her own letter is \( A \), then her name is \( A+M \). In general, if the founder is denoted by \( n=1 \) with name \( S \), for any \( i \) (\( 2\le i\le n \)) the name of Lady \( i \) is given by:

\( \text{Name}_i = \text{letter} + \text{Name}_{\text{mother}} \)

You are given the description of all the Royal Ladies and some query strings. For each query string \( s \), determine how many Royal Ladies have \( s \) as a prefix of their name.

For instance, consider a Royal Family with \( n = 10 \) ladies described below:

1. Lady 1 (founder): "S"
2. Lady 2: "YS" (formed as \( Y+S \))
3. Lady 3: "RYS" (formed as \( R+YS \))
4. Lady 4: "ERYS" (formed as \( E+RYS \))
5. Lady 5: "NERYS" (formed as \( N+ERYS \))
6. Lady 6: "ENERYS" (formed as \( E+NERYS \))
7. Lady 7: "AENERYS" (formed as \( A+ENERYS \))
8. Lady 8: "DAENERYS" (formed as \( D+AENERYS \))
9. Lady 9: "YAENERYS" (formed as \( Y+AENERYS \))
10. Lady 10: "RYAENERYS" (formed as \( R+YAENERYS \))

Given a query string \( s \), output the number of Royal Ladies whose names start with \( s \). For example, in the sample above:

• Query \( s = \texttt{RY} \) returns 2 (matches "RYS" and "RYAENERYS").
• Query \( s = \texttt{E} \) returns 2 (matches "ERYS" and "ENERYS").
• Query \( s = \texttt{N} \) returns 1 (matches "NERYS").
• Query \( s = \texttt{S} \) returns 1 (matches "S").
• Query \( s = \texttt{AY} \) returns 0.

inputFormat

The input consists of several parts:

1. An integer \( n \) representing the number of Royal Ladies.
2. The next \( n \) lines describe each Royal Lady in order from 1 to \( n \). For Lady 1 (the founder), the line contains a single uppercase letter representing her name. For each Lady \( i \) (where \( 2\le i\le n \)), the line contains two items: an integer representing the index of her mother, and an uppercase letter. The name of Lady \( i \) is the concatenation of this letter and her mother's name.
3. An integer \( q \) representing the number of queries.
4. The next \( q \) lines each contain a string \( s \) (composed of uppercase letters) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of Royal Ladies whose names have the query string as a prefix.

sample

10
S
1 Y
2 R
3 E
4 N
5 E
6 A
7 D
7 Y
9 R
5
RY
E
N
S
AY

2
2
1
1
0

</p>