Problem: Mishka's favourite experimental indie band has recently dropped a new album! Songs of that album share one gimmick. Each name s_i is one of the following types:

  * 1~c — a single lowercase Latin letter; 
  * 2~j~c — name s_j (1 ≤ j < i) with a single lowercase Latin letter appended to its end. 



Songs are numbered from 1 to n. It's guaranteed that the first song is always of type 1.

Vova is rather interested in the new album but he really doesn't have the time to listen to it entirely. Thus he asks Mishka some questions about it to determine if some song is worth listening to. Questions have the following format:

  * i~t — 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. 



Mishka doesn't question the purpose of that information, yet he struggles to provide it. Can you please help Mishka answer all Vova's questions?

Input

The first line contains a single integer n (1 ≤ n ≤ 4 ⋅ 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 ≤ j < i) with a single lowercase Latin letter appended to its end. 



The next line contains a single integer m (1 ≤ m ≤ 4 ⋅ 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 ≤ i ≤ n, 1 ≤ |t| ≤ 4 ⋅ 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 ⋅ 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.

Example

Input


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


Output


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". 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class G1207 {
	static class Scanner {
		BufferedReader br;
		StringTokenizer tk = new StringTokenizer("");

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		public int nextInt() throws IOException {
			if (tk.hasMoreTokens())
				return Integer.parseInt(tk.nextToken());
			tk = new StringTokenizer(br.readLine());
			return nextInt();
		}

		public long nextLong() throws IOException {
			if (tk.hasMoreTokens())
				return Long.parseLong(tk.nextToken());
			tk = new StringTokenizer(br.readLine());
			return nextLong();
		}

		public String next() throws IOException {
			if (tk.hasMoreTokens())
				return (tk.nextToken());
			tk = new StringTokenizer(br.readLine());
			return next();
		}

		public String nextLine() throws IOException {
			tk = new StringTokenizer("");
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			if (tk.hasMoreTokens())
				return Double.parseDouble(tk.nextToken());
			tk = new StringTokenizer(br.readLine());
			return nextDouble();
		}

		public char nextChar() throws IOException {
			if (tk.hasMoreTokens())
				return (tk.nextToken().charAt(0));
			tk = new StringTokenizer(br.readLine());
			return nextChar();
		}

		public int[] nextIntArray(int n) throws IOException {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n) throws IOException {
			long a[] = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public int[] nextIntArrayOneBased(int n) throws IOException {
			int a[] = new int[n + 1];
			for (int i = 1; i <= n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArrayOneBased(int n) throws IOException {
			long a[] = new long[n + 1];
			for (int i = 1; i <= n; i++)
				a[i] = nextLong();
			return a;
		}


	}

	public static void main(String args[]) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					solve();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();

	}
	static class SuffixAutomata{
		int trie[][];
		int suffixLink[];
		int next[][];
		int N=0;

		SuffixAutomata(){
			trie=new int[1000000][26];
			next=new int[1000000][26];
			suffixLink=new int[1000000];
		}

		int getNewNode(){
			return ++N;
		}

		int insert(String c){
			char s[]=c.toCharArray();
			int n=s.length;
			int node=0;
			for(int i=0;i<n;i++){
				if(trie[node][s[i]-'a']==0)
					trie[node][s[i]-'a']=getNewNode();
				node=trie[node][s[i]-'a'];
			}
			return node;
		}

		void createSuffixLinks(){
			next[0]=trie[0];
			ArrayDeque<Integer> queue = new ArrayDeque<>();
			for(int i=0;i<26;i++)
				if(trie[0][i]!=0)
					queue.add(trie[0][i]);

			while(!queue.isEmpty()){
				int node=queue.poll();
				//set the next values;
				for(int i=0;i<26;i++){
					int nextNode=trie[node][i];
					if(nextNode==0){
						next[node][i]=next[suffixLink[node]][i];
					}
					else{
						next[node][i]=nextNode;
						suffixLink[nextNode]=next[suffixLink[node]][i];
						queue.add(nextNode);
					}
				}
			}
		}
	}

	static class SegmentTree
	{
		int n;
		long tree[];
		public SegmentTree(int len)
		{
			n=len+31;
			tree=new long[n+1];
		}

		void incrementRange(int l,int r,long value)
		{
			add(l, value);
			add(r+1, -value);
		}
		void add(int i,long value)
		{
			for(;i<n;i+=i&-i)
				tree[i]+=value;
		}
		long query(int i)
		{
			long ans=0;
			for(;i>0;i-=i&-i)
				ans+=tree[i];
			return ans;
		}
	}

	static class Trie {
		int trie[][];
		int N = 0;

		Trie() {
			trie = new int[1000000][26];
		}

		int getNewNode(){
			return ++N;
		}

		int insert(int node, String c){
			char s[]=c.toCharArray();
			int n=s.length;
			for(int i=0;i<n;i++){
				if(trie[node][s[i]-'a']==0)
					trie[node][s[i]-'a']=getNewNode();
				node=trie[node][s[i]-'a'];
			}
			return node;
		}

		int insert(String c){
			return insert(0, c);
		}

	}
	static class Query{

		public Query(int queryNode) {
			this.queryNode = queryNode;
		}

		int queryNode;
		long ans;

	}

	static void addQuery(int queryIndex, int queryNode, int treeNode){
		q[queryIndex]=new Query(queryNode);
		if(!queries.containsKey(treeNode))
			queries.put(treeNode, new ArrayList<>());
		queries.get(treeNode).add(queryIndex);
	}
	static class Tree{
		ArrayList<Integer> g[];
		int time;
		int position[];
		int chainHead[];
		int subtreeSize[];
		int parent[];
		SegmentTree segmentTree;
		Tree(ArrayList<Integer> g[]){
			this.g=g;
			segmentTree=new SegmentTree(g.length);
			time=1;
			position=new int[g.length];
			chainHead=new int[g.length];
			subtreeSize=new int[g.length];
			parent=new int[g.length];
			calculateSubtreeSize(0);
			HLD(0,0);
		}
		int calculateSubtreeSize(int node){
			int ans=1;
			for(int x:g[node]){
				ans+=calculateSubtreeSize(x);
			}
			return subtreeSize[node]=ans;
		}
		void HLD(int node, int ch){
			position[node]=time++;
			chainHead[node]=ch;
			int specialChild=-1, maxSubtreeSize=0;
			for(int i:g[node]){
				parent[i]=node;
				if(subtreeSize[i] > maxSubtreeSize){
					maxSubtreeSize=subtreeSize[i];
					specialChild=i;
				}
			}
			if(specialChild!=-1)
				HLD(specialChild, ch);
			for(int i:g[node]){
				if(i==specialChild)
					continue;
				HLD(i,i);
			}
		}
		void addOnRootToNodePath(int node, long value){
			while(true){
				segmentTree.incrementRange(position[chainHead[node]], position[node], value);
				if(chainHead[node]==0)
					break;
				node=parent[chainHead[node]];
			}
		}

		int getNodeValue(int node){
			return (int)segmentTree.query(position[node]);
		}
	}
	static HashMap<Integer, Integer> map;
	static HashMap<Integer, Integer> querMap;
	static HashMap<Integer, ArrayList<Integer>> queries;
	static Query q[];
	static ArrayList<Integer> g[];
	static SuffixAutomata sa;
	static Trie trie;
	static Tree tree;
	static void sol(int node, int  matchNode){
		tree.addOnRootToNodePath(matchNode,1);

		//answer queries
		if(queries.containsKey(node)){
			for(int qi:queries.get(node)){
				q[qi].ans=tree.getNodeValue(q[qi].queryNode);
			}
		}

		for(int i=0;i<26;i++){
			if(trie.trie[node][i]!=0){
				sol(trie.trie[node][i], sa.next[matchNode][i]);
			}
		}

		tree.addOnRootToNodePath(matchNode,-1);

	}
	static void solve() throws IOException {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		sa=new SuffixAutomata();
		trie=new Trie();
		map=new HashMap<>();
		querMap=new HashMap<>();
		int n=in.nextInt();
		for(int i=0;i<n;i++){
			if(in.nextInt()==1){
				map.put(i+1, trie.insert(in.next()));
			}else{
				map.put(i+1, trie.insert(map.get(in.nextInt()), in.next()));
			}
		}
		int m=in.nextInt();
		queries=new HashMap<>();
		q=new Query[m];
		for(int i=0;i<m;i++){
			int treeNode = map.get(in.nextInt());
			int queryNode = sa.insert(in.next());
			addQuery(i, queryNode, treeNode);
		}
		sa.createSuffixLinks();
		g=new ArrayList[sa.N+1];
		for(int i=0;i<=sa.N;i++){
			g[i]=new ArrayList<>();
		}
		for(int i=1;i<=sa.N;i++)
			g[sa.suffixLink[i]].add(i);
		tree=new Tree(g);
		ArrayList<Integer> st=new ArrayList<>(), en=new ArrayList<>();
		sol(0,0);
		for(int i=0;i<m;i++)
			out.println(q[i].ans);
		out.close();
	}
}