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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
struct SuffixArray {
  vector<int> sa;
  vector<int> pos;
  vector<int> lcp;
  vector<int> id;
  int nid;
  vector<int> tmp;
  vector<int> cnt;
  vector<int> rmq;
  template <typename T, typename U>
  void buildsalcp(int n, int alph, T val, U nxt) {
    cnt = vector<int>(max(alph, n + 1), 0);
    sa = tmp = pos = lcp = vector<int>(n);
    id = vector<int>(n + 1);
    rmq = vector<int>(2 * (n + 1));
    for (int i = (0); i < (n); ++i) ++cnt[val(i)];
    for (int i = alph - 2; i >= 0; --i) cnt[i + 1] = cnt[i];
    cnt[0] = 0;
    for (int i = (0); i < (alph - 1); ++i) cnt[i + 1] += cnt[i];
    for (int i = (0); i < (n); ++i) sa[cnt[val(i)]++] = i;
    for (int i = (0); i < (n); ++i) pos[sa[i]] = i;
    nid = 0;
    id[0] = nid++;
    for (int i = (0); i < (n); ++i)
      if (i == 0 || val(sa[i]) != val(sa[i - 1]))
        id[sa[i] + 1] = nid++;
      else
        id[sa[i] + 1] = nid - 1;
    for (int i = (0); i < (n); ++i)
      lcp[i] = i + 1 < n && id[sa[i] + 1] == id[sa[i + 1] + 1] ? 1 : 0;
    for (int k = 0;; ++k) {
      bool done = true;
      for (int i = (0); i < (n); ++i)
        if (lcp[i] == 1 << k) done = false;
      if (done) break;
      for (int i = (0); i < (nid); ++i) cnt[i] = 0;
      for (int i = (0); i < (n); ++i) ++cnt[id[nxt(i, k) + 1]];
      for (int i = nid - 2; i >= 0; --i) cnt[i + 1] = cnt[i];
      cnt[0] = 0;
      for (int i = (0); i < (nid - 1); ++i) cnt[i + 1] += cnt[i];
      for (int i = (0); i < (n); ++i) tmp[cnt[id[nxt(i, k) + 1]]++] = i;
      for (int i = (0); i < (nid); ++i) cnt[i] = 0;
      for (int i = (0); i < (n); ++i) ++cnt[id[i + 1]];
      for (int i = nid - 2; i >= 0; --i) cnt[i + 1] = cnt[i];
      cnt[0] = 0;
      for (int i = (0); i < (nid - 1); ++i) cnt[i + 1] += cnt[i];
      for (int i = (0); i < (n); ++i) sa[cnt[id[tmp[i] + 1]]++] = tmp[i];
      for (int i = (0); i < (n); ++i) pos[sa[i]] = i;
      for (int i = (0); i < (n); ++i) rmq[n + i] = lcp[i];
      for (int i = n - 1; i >= 1; --i)
        rmq[i] = min(rmq[2 * i + 0], rmq[2 * i + 1]);
      auto getrmq = [&](int l, int r) {
        int ret = INT_MAX;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
          if (l & 1) ret = min(ret, rmq[l++]);
          if (r & 1) ret = min(ret, rmq[--r]);
        }
        return ret;
      };
      for (int i = (0); i < (n); ++i)
        if (lcp[i] == 1 << k) {
          int ii = nxt(sa[i], k), jj = nxt(sa[i + 1], k);
          if (ii == -1 || jj == -1) continue;
          ii = pos[ii], jj = pos[jj];
          if (ii > jj) swap(ii, jj);
          lcp[i] += id[sa[ii] + 1] == id[sa[jj] + 1] ? 1 << k : getrmq(ii, jj);
        }
      nid = 0;
      id[0] = nid++;
      for (int i = (0); i < (n); ++i)
        if (i == 0 || id[sa[i] + 1] != id[sa[i - 1] + 1] ||
            id[nxt(sa[i], k) + 1] != id[nxt(sa[i - 1], k) + 1])
          tmp[sa[i]] = nid++;
        else
          tmp[sa[i]] = nid - 1;
      for (int i = (0); i < (n); ++i) id[i + 1] = tmp[i];
    }
  }
  void buildsalcp(const string &s) {
    buildsalcp(((int)(s).size()), 256, [&](int off) { return (int)s[off]; },
               [&](int off, int k) {
                 return off + (1 << k) < ((int)(s).size()) ? off + (1 << k)
                                                           : -1;
               });
  }
  vector<int> bsllcp, bsrlcp;
  void buildbs() {
    bsllcp = bsrlcp = vector<int>(((int)(sa).size()));
    std::function<int(int, int)> rec = [&](int l, int r) -> int {
      if (r - l == 1) return l == -1 || r == ((int)(sa).size()) ? 0 : lcp[l];
      int m = l + (r - l) / 2;
      bsllcp[m] = rec(l, m);
      bsrlcp[m] = rec(m, r);
      return min(bsllcp[m], bsrlcp[m]);
    };
    rec(-1, ((int)(sa).size()));
  }
  template <typename T, typename U>
  int find(T getlcp, U cmp, bool upperbound = false) {
    int l = -1, r = ((int)(sa).size()), llcp = 0, rlcp = 0;
    while (r - l >= 2) {
      int m = l + (r - l) / 2;
      if (llcp >= rlcp) {
        if (bsllcp[m] > llcp)
          l = m;
        else if (bsllcp[m] < llcp)
          r = m, rlcp = bsllcp[m];
        else {
          int nlcp = getlcp(sa[m], llcp);
          if (cmp(sa[m], nlcp) < (!upperbound ? 0 : 1))
            l = m, llcp = nlcp;
          else
            r = m, rlcp = nlcp;
        }
      } else {
        if (bsrlcp[m] < rlcp)
          l = m, llcp = bsrlcp[m];
        else if (bsrlcp[m] > rlcp)
          r = m;
        else {
          int nlcp = getlcp(sa[m], rlcp);
          if (cmp(sa[m], nlcp) < (!upperbound ? 0 : 1))
            l = m, llcp = nlcp;
          else
            r = m, rlcp = nlcp;
        }
      }
    }
    return r;
  }
  int find(const string &s, const string &p, bool upperbound = false) {
    return find(
        [&](int i, int k) {
          while (i + k < ((int)(s).size()) && k < ((int)(p).size()) &&
                 s[i + k] == p[k])
            ++k;
          return k;
        },
        [&](int i, int k) {
          if (k == ((int)(p).size())) return 0;
          if (i + k == ((int)(s).size())) return -1;
          char a = s[i + k], b = p[k];
          if (a != b) return a < b ? -1 : +1;
          assert(false);
          return 0;
        },
        upperbound);
  }
  template <typename T, typename U>
  pair<int, int> findrange(T getlcp, U cmp) {
    return make_pair(find(getlcp, cmp, false), find(getlcp, cmp, true));
  }
  pair<int, int> findrange(const string &s, const string &p) {
    return findrange(
        [&](int i, int k) {
          while (i + k < ((int)(s).size()) && k < ((int)(p).size()) &&
                 s[i + k] == p[k])
            ++k;
          return k;
        },
        [&](int i, int k) {
          if (k == ((int)(p).size())) return 0;
          if (i + k == ((int)(s).size())) return -1;
          if (k == ((int)(p).size())) return +1;
          char a = s[i + k], b = p[k];
          if (a != b) return a < b ? -1 : +1;
          assert(false);
          return 0;
        });
  }
};
const int MAXSONG = 400000;
const int MAXQ = 400000;
const int MAXNODE = MAXSONG + 1;
const int MAXQLEN = 400000;
const int MAXLG = 18;
int nsong;
int par[MAXSONG];
char parc[MAXSONG];
int nq;
int qidx[MAXQ], qoff[MAXQ + 1], qlen[MAXQ];
char qs[MAXQLEN + 1];
int qans[MAXQ];
SuffixArray suff;
int up[MAXSONG][MAXLG + 1];
int ql[MAXQ], qr[MAXQ];
vector<int> qat[MAXSONG];
vector<int> ch[MAXSONG];
int bit[MAXSONG + 1];
int bget(int idx) {
  ++idx;
  int ret = 0;
  while (idx > 0) {
    ret += bit[idx];
    idx -= idx & -idx;
  }
  return ret;
}
void bmod(int idx, int by) {
  ++idx;
  while (idx <= nsong) {
    bit[idx] += by;
    idx += idx & -idx;
  }
}
void print() {
  for (int i = (0); i < (nsong); ++i) {
    int at = suff.sa[i];
    printf("%2d:", at);
    while (at != -1) {
      printf("%c", parc[at]);
      at = par[at];
    }
    printf(" (%d)\n", suff.lcp[i]);
  }
}
void dfs(int at) {
  bmod(suff.pos[at], +1);
  for (int _ = (0); _ < (((int)(qat[at]).size())); ++_) {
    int id = qat[at][_], l = ql[id], r = qr[id];
    qans[id] = bget(r - 1) - bget(l - 1);
  }
  for (int i = (0); i < (((int)(ch[at]).size())); ++i) {
    int to = ch[at][i];
    dfs(to);
  }
  bmod(suff.pos[at], -1);
}
int walk(int i, int steps) {
  for (int k = MAXLG; k >= 0; --k)
    if (steps & (1 << k))
      if (i != -1) i = up[i][k];
  return i;
}
void solve() {
  for (int i = (0); i < (nsong); ++i) up[i][0] = par[i];
  for (int k = (0); k < (MAXLG); ++k)
    for (int i = (0); i < (nsong); ++i)
      up[i][k + 1] = up[i][k] == -1 ? -1 : up[up[i][k]][k];
  suff.buildsalcp(
      nsong, 26, [&](int off) { return (int)(parc[off] - 'a'); },
      [&](int off, int k) { return up[off][k]; });
  suff.buildbs();
  for (int i = (0); i < (nsong); ++i) qat[i].clear();
  for (int i = (0); i < (nq); ++i) {
    string s(qs + qoff[i], qs + qoff[i] + qlen[i]);
    reverse(s.begin(), s.end());
    int l, r;
    tie(l, r) = suff.findrange(
        [&](int i, int k) {
          i = walk(i, k);
          while (i != -1 && k < ((int)(s).size()) && parc[i] == s[k])
            i = par[i], ++k;
          return k;
        },
        [&](int i, int k) {
          i = walk(i, k);
          if (k == ((int)(s).size())) return 0;
          if (i == -1) return -1;
          char a = parc[i], b = s[k];
          if (a != b) return a < b ? -1 : +1;
          assert(false);
          return 0;
        });
    ql[i] = l, qr[i] = r;
    qat[qidx[i]].push_back(i);
  }
  for (int i = (0); i < (nsong); ++i) ch[i].clear();
  for (int i = (0); i < (nsong); ++i)
    if (par[i] != -1) ch[par[i]].push_back(i);
  for (int i = (0); i <= (nsong); ++i) bit[i] = 0;
  for (int i = (0); i < (nsong); ++i)
    if (par[i] == -1) dfs(i);
}
void run() {
  scanf("%d", &nsong);
  for (int i = (0); i < (nsong); ++i) {
    int kind;
    scanf("%d", &kind);
    if (kind == 1)
      par[i] = -1;
    else
      scanf("%d", &par[i]), --par[i];
    scanf(" %c", &parc[i]);
  }
  scanf("%d", &nq);
  qoff[0] = 0;
  for (int i = (0); i < (nq); ++i) {
    scanf("%d%s", &qidx[i], qs + qoff[i]), --qidx[i];
    qlen[i] = strlen(qs + qoff[i]);
    qoff[i + 1] = qoff[i] + qlen[i];
  }
  solve();
  for (int i = (0); i < (nq); ++i) printf("%d\n", qans[i]);
}
int qansstupid[MAXQ];
void solvestupid() {
  for (int i = (0); i < (nq); ++i) {
    vector<char> tmp;
    for (int at = qidx[i]; at != -1; at = par[at]) tmp.push_back(parc[at]);
    reverse(tmp.begin(), tmp.end());
    qansstupid[i] = 0;
    for (int j = (0); j <= (((int)(tmp).size()) - qlen[i]); ++j) {
      bool ok = true;
      for (int k = (0); k < (qlen[i]); ++k)
        if (tmp[j + k] != qs[qoff[i] + k]) {
          ok = false;
          break;
        }
      if (ok) ++qansstupid[i];
    }
  }
}
void stress() {
  int mxsong = 1000, mxalph = 3, mxqlen = 5;
  nq = 1000;
  for (int rep = (0); rep < (100000); ++rep) {
    nsong = rand() % mxsong + 1;
    int alph = rand() % mxalph + 1;
    for (int i = (0); i < (nsong); ++i) {
      par[i] = rand() % (i + 1) - 1;
      parc[i] = 'a' + rand() % alph;
    }
    qoff[0] = 0;
    for (int i = (0); i < (nq); ++i) {
      qidx[i] = rand() % nsong;
      qlen[i] = rand() % mxqlen + 1;
      for (int j = (0); j < (qlen[i]); ++j)
        qs[qoff[i] + j] = 'a' + rand() % alph;
      qoff[i + 1] = qoff[i] + qlen[i];
    }
    qs[qoff[nq]] = '\0';
    solve();
    solvestupid();
    bool ok = true;
    for (int i = (0); i < (nq); ++i)
      if (qans[i] != qansstupid[i]) ok = false;
    if (ok) {
      if (rep % 100 == 0) printf(".");
      continue;
    }
    printf("err rep=%d\n", rep);
    printf("%d\n", nsong);
    for (int i = (0); i < (nsong); ++i)
      if (par[i] == -1)
        printf("%d %c\n", 1, parc[i]);
      else
        printf("%d %d %c\n", 2, par[i] + 1, parc[i]);
    printf("%d\n", nq);
    for (int i = (0); i < (nq); ++i) {
      printf("%d ", qidx[i] + 1);
      for (int j = (0); j < (qlen[i]); ++j) printf("%c", qs[qoff[i] + j]);
      puts("");
    }
    printf("have:");
    for (int i = (0); i < (nq); ++i) printf(" %d", qans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (nq); ++i) printf(" %d", qansstupid[i]);
    puts("");
    break;
  }
}
int main() {
  run();
  return 0;
}