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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
template <typename T>
struct fenwick_tree {
  int tree_n = 0;
  vector<T> tree;
  fenwick_tree(int n = 0) {
    if (n > 0) init(n);
  }
  void init(int n) {
    tree_n = n;
    tree.assign(tree_n + 1, 0);
  }
  template <typename T_array>
  void build(const T_array &initial) {
    assert((int)initial.size() == tree_n);
    for (int i = 1; i <= tree_n; i++) {
      tree[i] = initial[i - 1];
      for (int k = (i & -i) >> 1; k > 0; k >>= 1) tree[i] += tree[i - k];
    }
  }
  void update(int index, const T &change) {
    for (int i = index + 1; i <= tree_n; i += i & -i) tree[i] += change;
  }
  T query(int count) const {
    T sum = 0;
    for (int i = count; i > 0; i -= i & -i) sum += tree[i];
    return sum;
  }
};
template <typename T>
struct subtree_sum_DS {
  int n = 0;
  bool vertex_mode;
  vector<vector<int>> adj;
  vector<int> parent, depth;
  vector<int> tour_start, tour_end;
  vector<T> values;
  fenwick_tree<T> tree;
  subtree_sum_DS() {}
  subtree_sum_DS(int _n, bool _vertex_mode) { init(_n, _vertex_mode); }
  void init(int _n, bool _vertex_mode) {
    n = _n;
    vertex_mode = _vertex_mode;
    adj.assign(n, {});
    parent.resize(n);
    depth.resize(n);
    tour_start.assign(n, -INF);
    tour_end.assign(n, -INF);
    values.assign(n, 0);
    tree.init(n);
  }
  void init(const vector<vector<int>> &_adj, bool _vertex_mode) {
    init(_adj.size(), _vertex_mode);
    adj = _adj;
  }
  void add_edge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  void dfs(int node, int par) {
    static int tour;
    if (par < 0) tour = 0;
    parent[node] = par;
    depth[node] = par < 0 ? 0 : depth[par] + 1;
    tour_start[node] = tour++;
    for (int neighbor : adj[node])
      if (neighbor != par) dfs(neighbor, node);
    tour_end[node] = tour;
  }
  void build() {
    if (n == 0) return;
    dfs(0, -1);
  }
  void update_node(int node, T change) {
    values[node] += change;
    tree.update(tour_start[node], change);
  }
  void update_edge(int a, int b, T change) {
    if (depth[a] > depth[b]) swap(a, b);
    assert(depth[a] + 1 == depth[b]);
    update_node(b, change);
  }
  T query_subtree(int node) const {
    return tree.query(tour_end[node]) - tree.query(tour_start[node]) -
           (vertex_mode ? 0 : values[node]);
  }
};
struct aho_corasick {
  struct node {
    int suff = -1, dict = -1, depth = 0;
    int word_index = -1, word_count = 0;
    vector<pair<char, int>> children;
    vector<int> suffix_children;
    int get_child(char c) const {
      auto it = lower_bound(children.begin(), children.end(), make_pair(c, 0));
      if (it != children.end() && it->first == c) return it->second;
      return -1;
    }
  };
  vector<node> nodes;
  vector<string> words;
  vector<int> word_location;
  vector<int> word_indices_by_depth;
  vector<int> defer;
  aho_corasick(const vector<string> &_words = {}) {
    if (!_words.empty()) build(_words);
  }
  vector<vector<int>> build_suffix_adj() const {
    vector<vector<int>> adj(nodes.size());
    for (int i = 0; i < (int)nodes.size(); i++)
      adj[i] = nodes[i].suffix_children;
    return adj;
  }
  int get_or_add_child(int current, char c) {
    if (!nodes[current].children.empty() &&
        c == nodes[current].children.back().first)
      return nodes[current].children.back().second;
    int index = nodes.size();
    nodes[current].children.emplace_back(c, index);
    nodes.emplace_back();
    nodes.back().depth = nodes[current].depth + 1;
    return index;
  }
  int add_word(const string &word, int word_index) {
    assert(!nodes.empty());
    int current = 0;
    for (char c : word) current = get_or_add_child(current, c);
    if (nodes[current].word_index < 0) nodes[current].word_index = word_index;
    nodes[current].word_count++;
    return current;
  }
  int get_suffix_link(int location, char c) const {
    int child;
    while (location >= 0 && (child = nodes[location].get_child(c)) < 0)
      location = nodes[location].suff;
    return location < 0 ? 0 : child;
  }
  void build(const vector<string> &_words) {
    nodes.assign(1, node());
    words = _words;
    stable_sort(words.begin(), words.end());
    word_location.resize(words.size());
    defer.resize(words.size());
    int max_depth = 0;
    for (int i = 0; i < (int)words.size(); i++) {
      word_location[i] = add_word(words[i], i);
      max_depth = max(max_depth, nodes[word_location[i]].depth);
      defer[i] = i;
      if (i > 0 && words[i] == words[i - 1]) defer[i] = defer[i - 1];
    }
    vector<vector<int>> indices_by_depth(max_depth + 1, vector<int>());
    word_indices_by_depth.clear();
    for (int i = 0; i < (int)words.size(); i++)
      indices_by_depth[nodes[word_location[i]].depth].push_back(i);
    for (int depth = max_depth; depth >= 0; depth--)
      for (int index : indices_by_depth[depth])
        word_indices_by_depth.push_back(index);
    vector<int> q = {0};
    for (int i = 0; i < (int)q.size(); i++) {
      int current = q[i];
      for (pair<char, int> &p : nodes[current].children) {
        char c = p.first;
        int index = p.second;
        int suffix_parent = get_suffix_link(nodes[current].suff, c);
        nodes[index].suff = suffix_parent;
        nodes[suffix_parent].suffix_children.push_back(index);
        nodes[index].word_count += nodes[suffix_parent].word_count;
        nodes[index].dict = nodes[suffix_parent].word_index >= 0
                                ? suffix_parent
                                : nodes[suffix_parent].dict;
        q.push_back(index);
      }
    }
  }
  vector<int> count_matches(const string &text) const {
    vector<int> matches(words.size(), 0);
    int current = 0;
    for (char c : text) {
      current = get_suffix_link(current, c);
      int dict_node =
          nodes[current].word_index >= 0 ? current : nodes[current].dict;
      if (dict_node >= 0) matches[nodes[dict_node].word_index]++;
    }
    for (int word_index : word_indices_by_depth) {
      int location = word_location[word_index];
      int dict_node = nodes[location].dict;
      if (dict_node >= 0)
        matches[nodes[dict_node].word_index] += matches[word_index];
    }
    for (int i = 0; i < (int)words.size(); i++) matches[i] = matches[defer[i]];
    return matches;
  }
  long long count_total_matches(const string &text) const {
    long long matches = 0;
    int current = 0;
    for (char c : text) {
      current = get_suffix_link(current, c);
      matches += nodes[current].word_count;
    }
    return matches;
  }
};
const int NM_MAX = 4e5 + 5;
struct trie_node {
  map<char, trie_node *> children;
  vector<int> queries;
};
int N, M;
trie_node *root = nullptr;
vector<trie_node *> S;
vector<string> words;
vector<int> answers;
aho_corasick AC;
subtree_sum_DS<int> tree;
trie_node *add_child(trie_node *node, char c) {
  if (node->children.find(c) == node->children.end())
    node->children[c] = new trie_node();
  return node->children[c];
}
void dfs(trie_node *node, int location) {
  for (int q : node->queries) {
    int ac_index = lower_bound(AC.words.begin(), AC.words.end(), words[q]) -
                   AC.words.begin();
    int word_loc = AC.word_location[ac_index];
    answers[q] = tree.query_subtree(word_loc);
  }
  for (pair<char, trie_node *> p : node->children) {
    int next_location = AC.get_suffix_link(location, p.first);
    tree.update_node(next_location, +1);
    dfs(p.second, next_location);
    tree.update_node(next_location, -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  root = new trie_node();
  S.assign(N, nullptr);
  for (int i = 0; i < N; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      char c;
      cin >> c;
      S[i] = add_child(root, c);
    } else {
      int j;
      char c;
      cin >> j >> c;
      j--;
      S[i] = add_child(S[j], c);
    }
  }
  cin >> M;
  words.resize(M);
  answers.resize(M);
  for (int i = 0; i < M; i++) {
    int index;
    cin >> index >> words[i];
    index--;
    S[index]->queries.push_back(i);
  }
  AC.build(words);
  tree.init(AC.build_suffix_adj(), true);
  tree.build();
  dfs(root, 0);
  for (int answer : answers) cout << answer << '\n';
}