#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;
const int MAXHS = 200007;
const int MAXL = 19;
const int MAXS = 103;
const int MUL = 101;
const long long MOD = 10000000000000099;
struct qT {
  int u, v, lca;
  int s[MAXS];
  int sl;
  long long hsh, rh;
} que[MAXN];
struct qhT {
  int u, len, ans;
  long long hsh;
} qh[MAXN * 4];
struct eT {
  void setd(int _u, int _v, int _c, int _l) {
    u = _u, v = _v, ch = _c, last = _l;
  }
  int u, v, ch, last;
} edge[MAXN * 2];
class hashmapT {
 public:
  hashmapT() { clear(); }
  void clear() {
    memset(key, -1, sizeof(key));
    memset(val, 0, sizeof(val));
  }
  int& operator[](long long i) {
    int np = ((static_cast<long long>(i) * i + i) % MAXHS + MAXHS) % MAXHS;
    for (; (~key[np]) && (key[np] ^ i); (++np < MAXHS) ? np : (np -= MAXHS))
      ;
    key[np] = i;
    return val[np];
  }
  int operator[](long long i) const {
    int np = ((static_cast<long long>(i) * i + i) % MAXHS + MAXHS) % MAXHS;
    for (; (~key[np]) && (key[np] ^ i); (++np < MAXHS) ? np : (np -= MAXHS))
      ;
    return (key[np] == i) ? val[np] : 0;
  }

 private:
  long long key[MAXHS];
  int val[MAXHS];
} mp;
int n, q;
int kqh;
int ke, la[MAXN];
int fa[MAXN], fw[MAXN], lca[MAXN][MAXL], lev[MAXN];
long long up[MAXN][MAXS];
vector<int> qhr[MAXN];
int beg[MAXN];
int s[MAXN], rs[MAXN];
int fail[MAXN];
void init();
void input();
void work();
void predfs(int now, int nf, int nl, int pc);
void dfs(int now, int nf, int nl);
int getlca(int u, int v);
int goup(int u, int d);
int kmp(int s[], int n, int t[], int m);
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d", &n);
  int u, v;
  char s[13];
  memset(la, -1, sizeof(la));
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%s", &u, &v, s);
    edge[ke].setd(u, v, s[0] - 'a' + 7, la[u]);
    la[u] = ke++;
    edge[ke].setd(v, u, s[0] - 'a' + 7, la[v]);
    la[v] = ke++;
  }
  scanf("%d", &q);
  char ts[MAXS];
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%s", &que[i].u, &que[i].v, ts);
    que[i].sl = strlen(ts);
    for (int j = 0; j < que[i].sl; ++j) que[i].s[j] = ts[j] - 'a' + 7;
  }
}
void work() {
  for (int i = 1; i <= q; ++i) {
    for (int j = 0; j < que[i].sl; ++j)
      que[i].hsh =
          (static_cast<long long>(que[i].hsh) * MUL + que[i].s[j]) % MOD;
    for (int j = que[i].sl - 1; j >= 0; --j)
      que[i].rh = (static_cast<long long>(que[i].rh) * MUL + que[i].s[j]) % MOD;
  }
  predfs(1, 0, 1, 0);
  for (int j = 1; j < MAXL; ++j)
    for (int i = 1; i <= n; ++i)
      if (lca[i][j - 1]) lca[i][j] = lca[lca[i][j - 1]][j - 1];
  for (int i = 1; i <= q; ++i) {
    que[i].lca = getlca(que[i].u, que[i].v);
    if (lev[que[i].u] - lev[que[i].lca] >= que[i].sl) {
      qh[kqh].u = que[i].u, qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].rh;
      qhr[que[i].u].push_back(kqh);
      ++kqh;
      qh[kqh].u =
          goup(que[i].u, (lev[que[i].u] - lev[que[i].lca]) - que[i].sl + 1),
      qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].rh;
      qhr[qh[kqh].u].push_back(kqh);
      ++kqh;
    }
    if (lev[que[i].v] - lev[que[i].lca] >= que[i].sl) {
      qh[kqh].u = que[i].v, qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].hsh;
      qhr[que[i].v].push_back(kqh);
      ++kqh;
      qh[kqh].u =
          goup(que[i].v, (lev[que[i].v] - lev[que[i].lca]) - que[i].sl + 1),
      qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].hsh;
      qhr[qh[kqh].u].push_back(kqh);
      ++kqh;
    }
  }
  for (int i = 1; i <= n; ++i)
    sort(qhr[i].begin(), qhr[i].end(),
         [](int x, int y) { return qh[x].len < qh[y].len; });
  for (int i = 1; i < MAXS; ++i) {
    mp.clear();
    dfs(1, 0, i);
  }
  int qi = 0, ans, cu, cv, ls, lr;
  for (int i = 1; i <= q; ++i) {
    ans = 0;
    cu = que[i].u, cv = que[i].v;
    if (lev[que[i].u] - lev[que[i].lca] >= que[i].sl) {
      ans += qh[qi].ans - qh[qi + 1].ans;
      cu = qh[qi + 1].u;
      qi += 2;
    }
    if (lev[que[i].v] - lev[que[i].lca] >= que[i].sl) {
      ans += qh[qi].ans - qh[qi + 1].ans;
      cv = qh[qi + 1].u;
      qi += 2;
    }
    ls = lr = 0;
    while (cu ^ que[i].lca) s[ls++] = fw[cu], cu = fa[cu];
    while (cv ^ que[i].lca) rs[lr++] = fw[cv], cv = fa[cv];
    while (lr) s[ls++] = rs[--lr];
    ans += kmp(s, ls, que[i].s, que[i].sl);
    printf("%d\n", ans);
  }
}
void predfs(int now, int nf, int nl, int pc) {
  fw[now] = pc;
  fa[now] = lca[now][0] = nf;
  lev[now] = nl;
  for (int j = 1; j < (((nl) < (MAXS)) ? (nl) : (MAXS)); ++j)
    up[now][j] = (static_cast<long long>(up[nf][j - 1]) * MUL + pc) % MOD;
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ nf) predfs(edge[i].v, now, nl + 1, edge[i].ch);
}
void dfs(int now, int nf, int nl) {
  if (nl < lev[now]) ++mp[up[now][nl]];
  int x;
  while (beg[now] < qhr[now].size() && qh[x = qhr[now][beg[now]]].len == nl)
    qh[x].ans = mp[qh[x].hsh], ++beg[now];
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ nf) dfs(edge[i].v, now, nl);
  if (nl < lev[now]) --mp[up[now][nl]];
}
int getlca(int u, int v) {
  if (lev[u] < lev[v]) swap(u, v);
  u = goup(u, lev[u] - lev[v]);
  if (u == v) return u;
  for (int i = MAXL - 1; i >= 0; --i)
    if (lca[u][i] ^ lca[v][i]) u = lca[u][i], v = lca[v][i];
  return fa[u];
}
int goup(int u, int d) {
  for (int b = 0; d; d >>= 1, ++b)
    if (d & 1) u = lca[u][b];
  return u;
}
int kmp(int s[], int n, int t[], int m) {
  t[m] = -1;
  fail[0] = -1;
  int f = 0;
  for (int i = 1; i <= m; ++i) {
    fail[i] = f;
    if (t[i] == t[fail[i]]) fail[i] = fail[fail[i]];
    while ((~f) && t[i] != t[f]) f = fail[f];
    ++f;
  }
  int ni = 0, ans = 0;
  for (int i = 0; i < n; ++i) {
    while ((~ni) && s[i] != t[ni]) ni = fail[ni];
    ++ni;
    if (ni == m) ++ans;
  }
  return ans;
}

### Prompt

Please formulate a cpp solution to the following problem:

Since astronauts from BubbleCup XI mission finished their mission on the Moon and are big fans of famous singer, they decided to spend some fun time before returning to the Earth and hence created a so called "Moonwalk challenge" game.

Teams of astronauts are given the map of craters on the Moon and direct bidirectional paths from some craters to others that are safe for "Moonwalking". Each of those direct paths is colored in one color and there is unique path between each two craters. Goal of the game is to find two craters such that given array of colors appears most times as continuous subarray on the path between those two craters (overlapping appearances should be counted).

To help your favorite team win, you should make a program that, given the map, answers the queries of the following type: For two craters and array of colors answer how many times given array appears as continuous subarray on the path from the first crater to the second.

Colors are represented as lowercase English alphabet letters.

Input

In the first line, integer N (2 ≤ N ≤ 10^5) — number of craters on the Moon. Craters are numerated with numbers 1 to N.

In next N-1 lines, three values u, v, L (1 ≤ u, v ≤ N, L ∈ \\{a, ..., z\}) — denoting that there is a direct path with color L between craters u and v.

Next line contains integer Q (1 ≤ Q ≤ 10^5) — number of queries.

Next Q lines contain three values u, v (1 ≤ u, v ≤ N) and S (|S| ≤ 100), where u and v are the two cratersfor which you should find how many times array of colors S (represented as string) appears on the path from u to v. 

Output

For each query output one number that represents number of occurrences of array S on the path from u to v.

Example

Input

6
2 3 g
3 4 n
5 3 o
6 1 n
1 2 d
7
1 6 n
6 4 dg
6 4 n
2 5 og
1 2 d
6 5 go
2 3 g


Output

1
1
2
0
1
1
1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;
const int MAXHS = 200007;
const int MAXL = 19;
const int MAXS = 103;
const int MUL = 101;
const long long MOD = 10000000000000099;
struct qT {
  int u, v, lca;
  int s[MAXS];
  int sl;
  long long hsh, rh;
} que[MAXN];
struct qhT {
  int u, len, ans;
  long long hsh;
} qh[MAXN * 4];
struct eT {
  void setd(int _u, int _v, int _c, int _l) {
    u = _u, v = _v, ch = _c, last = _l;
  }
  int u, v, ch, last;
} edge[MAXN * 2];
class hashmapT {
 public:
  hashmapT() { clear(); }
  void clear() {
    memset(key, -1, sizeof(key));
    memset(val, 0, sizeof(val));
  }
  int& operator[](long long i) {
    int np = ((static_cast<long long>(i) * i + i) % MAXHS + MAXHS) % MAXHS;
    for (; (~key[np]) && (key[np] ^ i); (++np < MAXHS) ? np : (np -= MAXHS))
      ;
    key[np] = i;
    return val[np];
  }
  int operator[](long long i) const {
    int np = ((static_cast<long long>(i) * i + i) % MAXHS + MAXHS) % MAXHS;
    for (; (~key[np]) && (key[np] ^ i); (++np < MAXHS) ? np : (np -= MAXHS))
      ;
    return (key[np] == i) ? val[np] : 0;
  }

 private:
  long long key[MAXHS];
  int val[MAXHS];
} mp;
int n, q;
int kqh;
int ke, la[MAXN];
int fa[MAXN], fw[MAXN], lca[MAXN][MAXL], lev[MAXN];
long long up[MAXN][MAXS];
vector<int> qhr[MAXN];
int beg[MAXN];
int s[MAXN], rs[MAXN];
int fail[MAXN];
void init();
void input();
void work();
void predfs(int now, int nf, int nl, int pc);
void dfs(int now, int nf, int nl);
int getlca(int u, int v);
int goup(int u, int d);
int kmp(int s[], int n, int t[], int m);
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d", &n);
  int u, v;
  char s[13];
  memset(la, -1, sizeof(la));
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%s", &u, &v, s);
    edge[ke].setd(u, v, s[0] - 'a' + 7, la[u]);
    la[u] = ke++;
    edge[ke].setd(v, u, s[0] - 'a' + 7, la[v]);
    la[v] = ke++;
  }
  scanf("%d", &q);
  char ts[MAXS];
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%s", &que[i].u, &que[i].v, ts);
    que[i].sl = strlen(ts);
    for (int j = 0; j < que[i].sl; ++j) que[i].s[j] = ts[j] - 'a' + 7;
  }
}
void work() {
  for (int i = 1; i <= q; ++i) {
    for (int j = 0; j < que[i].sl; ++j)
      que[i].hsh =
          (static_cast<long long>(que[i].hsh) * MUL + que[i].s[j]) % MOD;
    for (int j = que[i].sl - 1; j >= 0; --j)
      que[i].rh = (static_cast<long long>(que[i].rh) * MUL + que[i].s[j]) % MOD;
  }
  predfs(1, 0, 1, 0);
  for (int j = 1; j < MAXL; ++j)
    for (int i = 1; i <= n; ++i)
      if (lca[i][j - 1]) lca[i][j] = lca[lca[i][j - 1]][j - 1];
  for (int i = 1; i <= q; ++i) {
    que[i].lca = getlca(que[i].u, que[i].v);
    if (lev[que[i].u] - lev[que[i].lca] >= que[i].sl) {
      qh[kqh].u = que[i].u, qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].rh;
      qhr[que[i].u].push_back(kqh);
      ++kqh;
      qh[kqh].u =
          goup(que[i].u, (lev[que[i].u] - lev[que[i].lca]) - que[i].sl + 1),
      qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].rh;
      qhr[qh[kqh].u].push_back(kqh);
      ++kqh;
    }
    if (lev[que[i].v] - lev[que[i].lca] >= que[i].sl) {
      qh[kqh].u = que[i].v, qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].hsh;
      qhr[que[i].v].push_back(kqh);
      ++kqh;
      qh[kqh].u =
          goup(que[i].v, (lev[que[i].v] - lev[que[i].lca]) - que[i].sl + 1),
      qh[kqh].len = que[i].sl, qh[kqh].hsh = que[i].hsh;
      qhr[qh[kqh].u].push_back(kqh);
      ++kqh;
    }
  }
  for (int i = 1; i <= n; ++i)
    sort(qhr[i].begin(), qhr[i].end(),
         [](int x, int y) { return qh[x].len < qh[y].len; });
  for (int i = 1; i < MAXS; ++i) {
    mp.clear();
    dfs(1, 0, i);
  }
  int qi = 0, ans, cu, cv, ls, lr;
  for (int i = 1; i <= q; ++i) {
    ans = 0;
    cu = que[i].u, cv = que[i].v;
    if (lev[que[i].u] - lev[que[i].lca] >= que[i].sl) {
      ans += qh[qi].ans - qh[qi + 1].ans;
      cu = qh[qi + 1].u;
      qi += 2;
    }
    if (lev[que[i].v] - lev[que[i].lca] >= que[i].sl) {
      ans += qh[qi].ans - qh[qi + 1].ans;
      cv = qh[qi + 1].u;
      qi += 2;
    }
    ls = lr = 0;
    while (cu ^ que[i].lca) s[ls++] = fw[cu], cu = fa[cu];
    while (cv ^ que[i].lca) rs[lr++] = fw[cv], cv = fa[cv];
    while (lr) s[ls++] = rs[--lr];
    ans += kmp(s, ls, que[i].s, que[i].sl);
    printf("%d\n", ans);
  }
}
void predfs(int now, int nf, int nl, int pc) {
  fw[now] = pc;
  fa[now] = lca[now][0] = nf;
  lev[now] = nl;
  for (int j = 1; j < (((nl) < (MAXS)) ? (nl) : (MAXS)); ++j)
    up[now][j] = (static_cast<long long>(up[nf][j - 1]) * MUL + pc) % MOD;
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ nf) predfs(edge[i].v, now, nl + 1, edge[i].ch);
}
void dfs(int now, int nf, int nl) {
  if (nl < lev[now]) ++mp[up[now][nl]];
  int x;
  while (beg[now] < qhr[now].size() && qh[x = qhr[now][beg[now]]].len == nl)
    qh[x].ans = mp[qh[x].hsh], ++beg[now];
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ nf) dfs(edge[i].v, now, nl);
  if (nl < lev[now]) --mp[up[now][nl]];
}
int getlca(int u, int v) {
  if (lev[u] < lev[v]) swap(u, v);
  u = goup(u, lev[u] - lev[v]);
  if (u == v) return u;
  for (int i = MAXL - 1; i >= 0; --i)
    if (lca[u][i] ^ lca[v][i]) u = lca[u][i], v = lca[v][i];
  return fa[u];
}
int goup(int u, int d) {
  for (int b = 0; d; d >>= 1, ++b)
    if (d & 1) u = lca[u][b];
  return u;
}
int kmp(int s[], int n, int t[], int m) {
  t[m] = -1;
  fail[0] = -1;
  int f = 0;
  for (int i = 1; i <= m; ++i) {
    fail[i] = f;
    if (t[i] == t[fail[i]]) fail[i] = fail[fail[i]];
    while ((~f) && t[i] != t[f]) f = fail[f];
    ++f;
  }
  int ni = 0, ans = 0;
  for (int i = 0; i < n; ++i) {
    while ((~ni) && s[i] != t[ni]) ni = fail[ni];
    ++ni;
    if (ni == m) ++ans;
  }
  return ans;
}

```