#include <bits/stdc++.h>
using namespace std;
const long long int inf = 1000000000;
const long long int mod = 1000000000 + 9;
inline void IO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline int dcmp(long double x) { return x < -1e-12 ? -1 : (x > 1e-12); }
template <class T>
inline int CHECK(T MASK, int i) {
  return (MASK >> i) & 1;
}
template <class T>
inline T ON(T MASK, int i) {
  return MASK | (T(1) << i);
}
template <class T>
inline T OFF(T MASK, int i) {
  return MASK & (~(T(1) << i));
}
template <typename T>
inline int CNT(T MASK) {
  if (numeric_limits<T>::digits <= numeric_limits<unsigned int>::digits)
    return __builtin_popcount(MASK);
  else
    return __builtin_popcountll(MASK);
}
template <class T>
inline int RIGHT(T MASK) {
  return log2(MASK & -MASK);
}
int dx4[] = {0, 0, -1, +1};
int dy4[] = {+1, -1, 0, 0};
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
inline void I(int& a) { scanf("%d", &a); }
inline void I(long long int& a) { scanf("%lld", &a); }
inline void I(unsigned long long int& a) { scanf("%llu", &a); }
inline void I(char* a) { scanf("%s", a); }
char Iarr[200];
inline void I(string& a) {
  scanf("%s", Iarr);
  a = Iarr;
}
inline void I(char& a) { scanf(" %c", &a); }
template <typename T, typename... Args>
void I(T& a, Args&... args) {
  I(a);
  I(args...);
}
inline void OUT(int a) { printf("%d", a); }
inline void OUT(long long int a) { printf("%lld", a); }
inline void OUT(const char* a) { printf("%s", a); }
inline void OUT(char* a) { printf("%s", a); }
inline void OUT(bool a) { printf("%d", a); }
inline void OUT(string a) {
  for (__typeof(a.end()) it = (a.begin()) - ((a.begin()) > (a.end()));
       it != (a.end()) - ((a.begin()) > (a.end()));
       it += 1 - 2 * ((a.begin()) > (a.end())))
    printf("%c", *it);
}
inline void OUT(unsigned long long int a) { printf("%llu", a); }
inline void OUT(char a) { printf("%c", a); }
template <typename T, typename... Args>
void OUT(T a, Args... args) {
  OUT(a);
  OUT(" ");
  OUT(args...);
}
template <typename... Args>
void O(Args... args) {
  OUT(args...);
  OUT("\n");
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << "{" << p.first << ", " << p.second << "}";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& a) {
  os << "[";
  for (int i = 0; i < (int)a.size(); i++) {
    if (i) os << ", ";
    os << a[i];
  }
  os << "]";
  return os;
}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cout << *it << " = " << a << endl;
  err(++it, args...);
}
const int M = 200010;
int N;
vector<int> Edge[100007 + 7];
int SubT[100007 + 7];
int Par[100007 + 7];
int Level[100007 + 7];
int nC;
int ChainLdr[100007 + 7];
int Chain[100007 + 7];
int nP;
int Pos[100007 + 7];
int rPos[100007 + 7];
unordered_map<long long int, char> color;
int Explore(int u, int p, int l) {
  SubT[u] = 1;
  Par[u] = p;
  Level[u] = l;
  int i;
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (p == v) continue;
    SubT[u] += Explore(v, u, l + 1);
  }
  return SubT[u];
}
void HeavyLight(int u, int k, bool IsL) {
  if (IsL) {
    k = ++nC;
    ChainLdr[k] = u;
  }
  Chain[u] = k;
  Pos[u] = ++nP;
  rPos[nP] = u;
  int i, mx = -1;
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (Par[u] == v) continue;
    if (mx == -1)
      mx = v;
    else if (SubT[v] > SubT[mx])
      mx = v;
  }
  if (mx == -1) return;
  HeavyLight(mx, k, false);
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (Par[u] == v || mx == v) continue;
    HeavyLight(v, 0, true);
  }
}
int LCA(int u, int v) {
  while (Chain[u] != Chain[v]) {
    if (Level[ChainLdr[Chain[u]]] < Level[ChainLdr[Chain[v]]]) {
      v = Par[ChainLdr[Chain[v]]];
    } else {
      u = Par[ChainLdr[Chain[u]]];
    }
  }
  if (Level[u] < Level[v])
    return u;
  else
    return v;
}
const long long int mod1 = 1000000007;
const long long int mod2 = 1000000009;
const long long int base = 347;
long long int H1(string s) {
  long long int ret = 0;
  for (char c : s) {
    ret = ret * base + c;
    ret %= mod1;
  }
  return ret;
}
long long int H2(string s) {
  long long int ret = 0;
  for (char c : s) {
    ret = ret * base + c;
    ret %= mod2;
  }
  return ret;
}
struct Hash {
  int h1, h2;
  int val;
  Hash(int a, int b, int d) {
    h1 = a;
    h2 = b;
    val = d;
  }
};
bool operator<(const Hash& obj1, const Hash& obj2) {
  if (obj1.h1 < obj2.h1)
    return 1;
  else if (obj1.h1 > obj2.h1)
    return 0;
  else if (obj1.h2 < obj2.h2)
    return 1;
  else if (obj1.h2 > obj2.h2)
    return 0;
  else if (obj1.val < obj2.val)
    return 1;
  else
    return 0;
}
bool operator==(const Hash& obj1, const Hash& obj2) {
  if (obj1.h1 == obj2.h1 && obj1.h2 == obj2.h2 && obj1.val == obj2.val)
    return 1;
  return 0;
}
bool operator>(const Hash& obj1, const Hash& obj2) {
  if (!(obj1 < obj2) && !(obj1 == obj2)) return 1;
  return 0;
}
bool operator<=(const Hash& obj1, const Hash& obj2) { return !(obj1 > obj2); }
bool operator>=(const Hash& obj1, const Hash& obj2) { return !(obj1 < obj2); }
bool lesss(const Hash& obj1, const Hash& obj2) { return (obj1 < obj2); }
set<long long int> exists;
long long int mak(long long int a, long long int b) {
  return a * 1000000021 + b;
}
long long int mk(int a, int b) { return (long long int)a * 1000000 + b; }
vector<Hash> v[100007 + 7];
void g() {
  for (int chn = 1; chn <= nC; chn++) {
    int stChn = Pos[ChainLdr[chn]];
    int low = stChn, high = nP;
    while (low < high) {
      int mid = (low + high + 1) / 2;
      if (Chain[rPos[mid]] != chn)
        high = mid - 1;
      else
        low = mid;
    }
    int enChn = low;
    if (Par[rPos[stChn]] != rPos[stChn]) {
      long long int h1 = 0, h2 = 0;
      for (int i = stChn, co = 0; i <= enChn && co < 100; i++, co++) {
        if (i == stChn) {
          h1 = h1 * base + color[mk(Par[rPos[stChn]], rPos[stChn])];
        } else
          h1 = h1 * base + color[mk(rPos[i - 1], rPos[i])];
        h1 %= mod1;
        if (i == stChn) {
          h2 = h2 * base + color[mk(Par[rPos[stChn]], rPos[stChn])];
        } else
          h2 = h2 * base + color[mk(rPos[i - 1], rPos[i])];
        h2 %= mod2;
        if (exists.find(mak(h1, h2)) != exists.end())
          v[chn].push_back(Hash(h1, h2, i));
      }
    }
    for (int i = stChn; i <= enChn; i++) {
      long long int h1 = 0, h2 = 0;
      int co = 0;
      int curr = i;
      while (co < 101 && curr <= enChn) {
        if (co) {
          h1 = h1 * base + color[mk(rPos[curr - 1], rPos[curr])];
          h1 %= mod1;
          h2 = h2 * base + color[mk(rPos[curr - 1], rPos[curr])];
          h2 %= mod2;
          if (exists.find(mak(h1, h2)) != exists.end())
            v[chn].push_back(Hash(h1, h2, curr));
        }
        curr++;
        co++;
      }
    }
    sort(v[chn].begin(), v[chn].end(), lesss);
  }
}
int query1(int down, int up, string s) {
  int ret = 0;
  int h1 = H1(s);
  int h2 = H2(s);
  int x = down;
  int curr = Chain[x];
  while (x != up) {
    if (Chain[x] == Chain[up]) {
      Hash a(h1, h2, Pos[x]);
      Hash b(h1, h2, Pos[up] + (int)s.size());
      if (b <= a) {
        auto it = upper_bound(v[Chain[x]].begin(), v[Chain[x]].end(), a);
        auto it1 = lower_bound(v[Chain[x]].begin(), v[Chain[x]].end(), b);
        ret += it - it1;
      }
      x = up;
    } else {
      Hash a(h1, h2, Pos[x]);
      Hash b(h1, h2, Pos[ChainLdr[Chain[x]]] + (int)s.size() - 1);
      if (b <= a) {
        auto it = upper_bound(v[Chain[x]].begin(), v[Chain[x]].end(), a);
        auto it1 = lower_bound(v[Chain[x]].begin(), v[Chain[x]].end(), b);
        ret += it - it1;
      }
      x = Par[ChainLdr[Chain[x]]];
    }
  }
  return ret;
}
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) ++j;
    pi[i] = j;
  }
  return pi;
}
int kmp(string txt, string pat, vector<int> pi) {
  int match = 0;
  int i = 0, j = 0;
  while (i < txt.size()) {
    if (j == pat.size()) {
      match++;
      j = pi[j - 1];
    } else if (txt[i] == pat[j]) {
      i++;
      j++;
    } else {
      if (!j)
        i++;
      else
        j = pi[j - 1];
    }
  }
  if (j == pat.size()) {
    match++;
  }
  return match;
}
int query2(vector<int> v1, int st, int en, string org) {
  string s;
  set<int> sett;
  int j;
  for (int i = 0; i < (int)v1.size(); i++) {
    if (v1[i] != st && v1[i] != en) {
      vector<int> vtemp;
      int prev;
      if (i == 0)
        prev = st;
      else
        prev = v1[i - 1];
      int curr = v1[i];
      int len = 0;
      j = i;
      while (len < (int)org.size() - 1 && sett.find(curr) == sett.end()) {
        if (curr != v1[i]) sett.insert(curr);
        int found = -1;
        int same = -1;
        for (int u : Edge[curr]) {
          if (Chain[u] == Chain[curr]) {
            if (Level[u] > Level[curr] && Level[prev] > Level[curr]) same = u;
            if (Level[u] < Level[curr] && Level[prev] < Level[curr]) same = u;
          }
          if (Chain[u] == Chain[prev]) {
            if (Chain[u] == Chain[curr]) {
              if (Level[u] > Level[curr] && Level[prev] > Level[curr]) {
                found = u;
                break;
              }
              if (Level[u] < Level[curr] && Level[prev] < Level[curr]) {
                found = u;
                break;
              }
            } else {
              found = u;
              break;
            }
          }
        }
        if (found == -1) {
          if (same == -1)
            break;
          else {
            vtemp.push_back(same);
            curr = same;
          }
        } else {
          vtemp.push_back(found);
          curr = found;
        }
        len++;
        if (curr == st) {
          break;
        } else if (curr == prev) {
          int temp = prev;
          j--;
          if (j == 0)
            prev = st;
          else
            prev = v1[j - 1];
          curr = temp;
        }
      }
      reverse(vtemp.begin(), vtemp.end());
      if (sett.find(v1[i]) == sett.end()) {
        vtemp.push_back(v1[i]);
        sett.insert(v1[i]);
      }
      int next;
      if (i == (int)v1.size() - 1)
        next = en;
      else
        next = v1[i + 1];
      curr = v1[i];
      len = 0;
      j = i;
      while (len < (int)org.size() - 1) {
        int found = -1;
        int same = -1;
        for (int u : Edge[curr]) {
          if (Chain[u] == Chain[curr]) {
            if (Level[u] > Level[curr] && Level[next] > Level[curr]) same = u;
            if (Level[u] < Level[curr] && Level[next] < Level[curr]) same = u;
          }
          if (Chain[u] == Chain[next]) {
            if (Chain[u] == Chain[curr]) {
              if (Level[u] > Level[curr] && Level[next] > Level[curr]) {
                found = u;
                break;
              }
              if (Level[u] < Level[curr] && Level[next] < Level[curr]) {
                found = u;
                break;
              }
            } else {
              found = u;
              break;
            }
          }
        }
        if (found == -1) {
          if (same == -1)
            break;
          else {
            vtemp.push_back(same);
            curr = same;
          }
        } else {
          vtemp.push_back(found);
          curr = found;
        }
        len++;
        if (curr == en) {
          break;
        } else if (curr == next) {
          int temp = next;
          j++;
          if (j == (int)v1.size() - 1)
            next = en;
          else
            next = v1[j + 1];
          curr = temp;
        }
      }
      s += "$#";
      for (int i = 1; i < (int)vtemp.size(); i++) {
        s += color[mk(vtemp[i - 1], vtemp[i])];
      }
      s += "$#";
    }
  }
  if ((int)s.size() && (int)org.size()) {
    vector<int> pf = prefix_function(org);
    return kmp(s, org, pf);
  } else
    return 0;
}
int query(int st, int en, string s) {
  int lca = LCA(st, en);
  int ans = 0;
  string rev = s;
  reverse(rev.begin(), rev.end());
  ans += query1(st, lca, rev);
  ans += query1(en, lca, s);
  vector<int> points;
  int temp = st;
  bool flag = 0;
  while (temp != lca) {
    if (Chain[temp] != Chain[lca]) {
      points.push_back(Par[ChainLdr[Chain[temp]]]);
      temp = Par[ChainLdr[Chain[temp]]];
      if (temp == lca) flag = 1;
    } else {
      temp = lca;
    }
  }
  vector<int> points1;
  temp = en;
  while (temp != lca) {
    if (Chain[temp] != Chain[lca]) {
      temp = Par[ChainLdr[Chain[temp]]];
      if (temp == lca) {
        if (!flag) points1.push_back(temp);
      } else
        points1.push_back(temp);
    } else {
      temp = lca;
    }
  }
  reverse(points1.begin(), points1.end());
  for (int x : points1) points.push_back(x);
  ans += query2(points, st, en, s);
  return ans;
}
int main() {
  color.reserve(262144);
  color.max_load_factor(0.25);
  I(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    char c;
    I(u, v, c);
    u--;
    v--;
    Edge[u].push_back(v);
    Edge[v].push_back(u);
    color[mk(u, v)] = c;
    color[mk(v, u)] = c;
  }
  Explore(0, 0, 0);
  HeavyLight(0, 0, true);
  int q;
  I(q);
  vector<pair<pair<int, int>, string> > temp;
  while (q--) {
    int st, en;
    string s;
    I(st, en, s);
    st--;
    en--;
    temp.push_back(make_pair(make_pair(st, en), s));
    exists.insert(mak(H1(s), H2(s)));
    reverse(s.begin(), s.end());
    exists.insert(mak(H1(s), H2(s)));
  }
  g();
  for (auto it : temp) {
    O(query(it.first.first, it.first.second, it.second));
  }
  return 0;
}

### Prompt

Generate 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 long long int inf = 1000000000;
const long long int mod = 1000000000 + 9;
inline void IO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline int dcmp(long double x) { return x < -1e-12 ? -1 : (x > 1e-12); }
template <class T>
inline int CHECK(T MASK, int i) {
  return (MASK >> i) & 1;
}
template <class T>
inline T ON(T MASK, int i) {
  return MASK | (T(1) << i);
}
template <class T>
inline T OFF(T MASK, int i) {
  return MASK & (~(T(1) << i));
}
template <typename T>
inline int CNT(T MASK) {
  if (numeric_limits<T>::digits <= numeric_limits<unsigned int>::digits)
    return __builtin_popcount(MASK);
  else
    return __builtin_popcountll(MASK);
}
template <class T>
inline int RIGHT(T MASK) {
  return log2(MASK & -MASK);
}
int dx4[] = {0, 0, -1, +1};
int dy4[] = {+1, -1, 0, 0};
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
inline void I(int& a) { scanf("%d", &a); }
inline void I(long long int& a) { scanf("%lld", &a); }
inline void I(unsigned long long int& a) { scanf("%llu", &a); }
inline void I(char* a) { scanf("%s", a); }
char Iarr[200];
inline void I(string& a) {
  scanf("%s", Iarr);
  a = Iarr;
}
inline void I(char& a) { scanf(" %c", &a); }
template <typename T, typename... Args>
void I(T& a, Args&... args) {
  I(a);
  I(args...);
}
inline void OUT(int a) { printf("%d", a); }
inline void OUT(long long int a) { printf("%lld", a); }
inline void OUT(const char* a) { printf("%s", a); }
inline void OUT(char* a) { printf("%s", a); }
inline void OUT(bool a) { printf("%d", a); }
inline void OUT(string a) {
  for (__typeof(a.end()) it = (a.begin()) - ((a.begin()) > (a.end()));
       it != (a.end()) - ((a.begin()) > (a.end()));
       it += 1 - 2 * ((a.begin()) > (a.end())))
    printf("%c", *it);
}
inline void OUT(unsigned long long int a) { printf("%llu", a); }
inline void OUT(char a) { printf("%c", a); }
template <typename T, typename... Args>
void OUT(T a, Args... args) {
  OUT(a);
  OUT(" ");
  OUT(args...);
}
template <typename... Args>
void O(Args... args) {
  OUT(args...);
  OUT("\n");
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << "{" << p.first << ", " << p.second << "}";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& a) {
  os << "[";
  for (int i = 0; i < (int)a.size(); i++) {
    if (i) os << ", ";
    os << a[i];
  }
  os << "]";
  return os;
}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cout << *it << " = " << a << endl;
  err(++it, args...);
}
const int M = 200010;
int N;
vector<int> Edge[100007 + 7];
int SubT[100007 + 7];
int Par[100007 + 7];
int Level[100007 + 7];
int nC;
int ChainLdr[100007 + 7];
int Chain[100007 + 7];
int nP;
int Pos[100007 + 7];
int rPos[100007 + 7];
unordered_map<long long int, char> color;
int Explore(int u, int p, int l) {
  SubT[u] = 1;
  Par[u] = p;
  Level[u] = l;
  int i;
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (p == v) continue;
    SubT[u] += Explore(v, u, l + 1);
  }
  return SubT[u];
}
void HeavyLight(int u, int k, bool IsL) {
  if (IsL) {
    k = ++nC;
    ChainLdr[k] = u;
  }
  Chain[u] = k;
  Pos[u] = ++nP;
  rPos[nP] = u;
  int i, mx = -1;
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (Par[u] == v) continue;
    if (mx == -1)
      mx = v;
    else if (SubT[v] > SubT[mx])
      mx = v;
  }
  if (mx == -1) return;
  HeavyLight(mx, k, false);
  for (i = 0; i < Edge[u].size(); i++) {
    int v = Edge[u][i];
    if (Par[u] == v || mx == v) continue;
    HeavyLight(v, 0, true);
  }
}
int LCA(int u, int v) {
  while (Chain[u] != Chain[v]) {
    if (Level[ChainLdr[Chain[u]]] < Level[ChainLdr[Chain[v]]]) {
      v = Par[ChainLdr[Chain[v]]];
    } else {
      u = Par[ChainLdr[Chain[u]]];
    }
  }
  if (Level[u] < Level[v])
    return u;
  else
    return v;
}
const long long int mod1 = 1000000007;
const long long int mod2 = 1000000009;
const long long int base = 347;
long long int H1(string s) {
  long long int ret = 0;
  for (char c : s) {
    ret = ret * base + c;
    ret %= mod1;
  }
  return ret;
}
long long int H2(string s) {
  long long int ret = 0;
  for (char c : s) {
    ret = ret * base + c;
    ret %= mod2;
  }
  return ret;
}
struct Hash {
  int h1, h2;
  int val;
  Hash(int a, int b, int d) {
    h1 = a;
    h2 = b;
    val = d;
  }
};
bool operator<(const Hash& obj1, const Hash& obj2) {
  if (obj1.h1 < obj2.h1)
    return 1;
  else if (obj1.h1 > obj2.h1)
    return 0;
  else if (obj1.h2 < obj2.h2)
    return 1;
  else if (obj1.h2 > obj2.h2)
    return 0;
  else if (obj1.val < obj2.val)
    return 1;
  else
    return 0;
}
bool operator==(const Hash& obj1, const Hash& obj2) {
  if (obj1.h1 == obj2.h1 && obj1.h2 == obj2.h2 && obj1.val == obj2.val)
    return 1;
  return 0;
}
bool operator>(const Hash& obj1, const Hash& obj2) {
  if (!(obj1 < obj2) && !(obj1 == obj2)) return 1;
  return 0;
}
bool operator<=(const Hash& obj1, const Hash& obj2) { return !(obj1 > obj2); }
bool operator>=(const Hash& obj1, const Hash& obj2) { return !(obj1 < obj2); }
bool lesss(const Hash& obj1, const Hash& obj2) { return (obj1 < obj2); }
set<long long int> exists;
long long int mak(long long int a, long long int b) {
  return a * 1000000021 + b;
}
long long int mk(int a, int b) { return (long long int)a * 1000000 + b; }
vector<Hash> v[100007 + 7];
void g() {
  for (int chn = 1; chn <= nC; chn++) {
    int stChn = Pos[ChainLdr[chn]];
    int low = stChn, high = nP;
    while (low < high) {
      int mid = (low + high + 1) / 2;
      if (Chain[rPos[mid]] != chn)
        high = mid - 1;
      else
        low = mid;
    }
    int enChn = low;
    if (Par[rPos[stChn]] != rPos[stChn]) {
      long long int h1 = 0, h2 = 0;
      for (int i = stChn, co = 0; i <= enChn && co < 100; i++, co++) {
        if (i == stChn) {
          h1 = h1 * base + color[mk(Par[rPos[stChn]], rPos[stChn])];
        } else
          h1 = h1 * base + color[mk(rPos[i - 1], rPos[i])];
        h1 %= mod1;
        if (i == stChn) {
          h2 = h2 * base + color[mk(Par[rPos[stChn]], rPos[stChn])];
        } else
          h2 = h2 * base + color[mk(rPos[i - 1], rPos[i])];
        h2 %= mod2;
        if (exists.find(mak(h1, h2)) != exists.end())
          v[chn].push_back(Hash(h1, h2, i));
      }
    }
    for (int i = stChn; i <= enChn; i++) {
      long long int h1 = 0, h2 = 0;
      int co = 0;
      int curr = i;
      while (co < 101 && curr <= enChn) {
        if (co) {
          h1 = h1 * base + color[mk(rPos[curr - 1], rPos[curr])];
          h1 %= mod1;
          h2 = h2 * base + color[mk(rPos[curr - 1], rPos[curr])];
          h2 %= mod2;
          if (exists.find(mak(h1, h2)) != exists.end())
            v[chn].push_back(Hash(h1, h2, curr));
        }
        curr++;
        co++;
      }
    }
    sort(v[chn].begin(), v[chn].end(), lesss);
  }
}
int query1(int down, int up, string s) {
  int ret = 0;
  int h1 = H1(s);
  int h2 = H2(s);
  int x = down;
  int curr = Chain[x];
  while (x != up) {
    if (Chain[x] == Chain[up]) {
      Hash a(h1, h2, Pos[x]);
      Hash b(h1, h2, Pos[up] + (int)s.size());
      if (b <= a) {
        auto it = upper_bound(v[Chain[x]].begin(), v[Chain[x]].end(), a);
        auto it1 = lower_bound(v[Chain[x]].begin(), v[Chain[x]].end(), b);
        ret += it - it1;
      }
      x = up;
    } else {
      Hash a(h1, h2, Pos[x]);
      Hash b(h1, h2, Pos[ChainLdr[Chain[x]]] + (int)s.size() - 1);
      if (b <= a) {
        auto it = upper_bound(v[Chain[x]].begin(), v[Chain[x]].end(), a);
        auto it1 = lower_bound(v[Chain[x]].begin(), v[Chain[x]].end(), b);
        ret += it - it1;
      }
      x = Par[ChainLdr[Chain[x]]];
    }
  }
  return ret;
}
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) ++j;
    pi[i] = j;
  }
  return pi;
}
int kmp(string txt, string pat, vector<int> pi) {
  int match = 0;
  int i = 0, j = 0;
  while (i < txt.size()) {
    if (j == pat.size()) {
      match++;
      j = pi[j - 1];
    } else if (txt[i] == pat[j]) {
      i++;
      j++;
    } else {
      if (!j)
        i++;
      else
        j = pi[j - 1];
    }
  }
  if (j == pat.size()) {
    match++;
  }
  return match;
}
int query2(vector<int> v1, int st, int en, string org) {
  string s;
  set<int> sett;
  int j;
  for (int i = 0; i < (int)v1.size(); i++) {
    if (v1[i] != st && v1[i] != en) {
      vector<int> vtemp;
      int prev;
      if (i == 0)
        prev = st;
      else
        prev = v1[i - 1];
      int curr = v1[i];
      int len = 0;
      j = i;
      while (len < (int)org.size() - 1 && sett.find(curr) == sett.end()) {
        if (curr != v1[i]) sett.insert(curr);
        int found = -1;
        int same = -1;
        for (int u : Edge[curr]) {
          if (Chain[u] == Chain[curr]) {
            if (Level[u] > Level[curr] && Level[prev] > Level[curr]) same = u;
            if (Level[u] < Level[curr] && Level[prev] < Level[curr]) same = u;
          }
          if (Chain[u] == Chain[prev]) {
            if (Chain[u] == Chain[curr]) {
              if (Level[u] > Level[curr] && Level[prev] > Level[curr]) {
                found = u;
                break;
              }
              if (Level[u] < Level[curr] && Level[prev] < Level[curr]) {
                found = u;
                break;
              }
            } else {
              found = u;
              break;
            }
          }
        }
        if (found == -1) {
          if (same == -1)
            break;
          else {
            vtemp.push_back(same);
            curr = same;
          }
        } else {
          vtemp.push_back(found);
          curr = found;
        }
        len++;
        if (curr == st) {
          break;
        } else if (curr == prev) {
          int temp = prev;
          j--;
          if (j == 0)
            prev = st;
          else
            prev = v1[j - 1];
          curr = temp;
        }
      }
      reverse(vtemp.begin(), vtemp.end());
      if (sett.find(v1[i]) == sett.end()) {
        vtemp.push_back(v1[i]);
        sett.insert(v1[i]);
      }
      int next;
      if (i == (int)v1.size() - 1)
        next = en;
      else
        next = v1[i + 1];
      curr = v1[i];
      len = 0;
      j = i;
      while (len < (int)org.size() - 1) {
        int found = -1;
        int same = -1;
        for (int u : Edge[curr]) {
          if (Chain[u] == Chain[curr]) {
            if (Level[u] > Level[curr] && Level[next] > Level[curr]) same = u;
            if (Level[u] < Level[curr] && Level[next] < Level[curr]) same = u;
          }
          if (Chain[u] == Chain[next]) {
            if (Chain[u] == Chain[curr]) {
              if (Level[u] > Level[curr] && Level[next] > Level[curr]) {
                found = u;
                break;
              }
              if (Level[u] < Level[curr] && Level[next] < Level[curr]) {
                found = u;
                break;
              }
            } else {
              found = u;
              break;
            }
          }
        }
        if (found == -1) {
          if (same == -1)
            break;
          else {
            vtemp.push_back(same);
            curr = same;
          }
        } else {
          vtemp.push_back(found);
          curr = found;
        }
        len++;
        if (curr == en) {
          break;
        } else if (curr == next) {
          int temp = next;
          j++;
          if (j == (int)v1.size() - 1)
            next = en;
          else
            next = v1[j + 1];
          curr = temp;
        }
      }
      s += "$#";
      for (int i = 1; i < (int)vtemp.size(); i++) {
        s += color[mk(vtemp[i - 1], vtemp[i])];
      }
      s += "$#";
    }
  }
  if ((int)s.size() && (int)org.size()) {
    vector<int> pf = prefix_function(org);
    return kmp(s, org, pf);
  } else
    return 0;
}
int query(int st, int en, string s) {
  int lca = LCA(st, en);
  int ans = 0;
  string rev = s;
  reverse(rev.begin(), rev.end());
  ans += query1(st, lca, rev);
  ans += query1(en, lca, s);
  vector<int> points;
  int temp = st;
  bool flag = 0;
  while (temp != lca) {
    if (Chain[temp] != Chain[lca]) {
      points.push_back(Par[ChainLdr[Chain[temp]]]);
      temp = Par[ChainLdr[Chain[temp]]];
      if (temp == lca) flag = 1;
    } else {
      temp = lca;
    }
  }
  vector<int> points1;
  temp = en;
  while (temp != lca) {
    if (Chain[temp] != Chain[lca]) {
      temp = Par[ChainLdr[Chain[temp]]];
      if (temp == lca) {
        if (!flag) points1.push_back(temp);
      } else
        points1.push_back(temp);
    } else {
      temp = lca;
    }
  }
  reverse(points1.begin(), points1.end());
  for (int x : points1) points.push_back(x);
  ans += query2(points, st, en, s);
  return ans;
}
int main() {
  color.reserve(262144);
  color.max_load_factor(0.25);
  I(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    char c;
    I(u, v, c);
    u--;
    v--;
    Edge[u].push_back(v);
    Edge[v].push_back(u);
    color[mk(u, v)] = c;
    color[mk(v, u)] = c;
  }
  Explore(0, 0, 0);
  HeavyLight(0, 0, true);
  int q;
  I(q);
  vector<pair<pair<int, int>, string> > temp;
  while (q--) {
    int st, en;
    string s;
    I(st, en, s);
    st--;
    en--;
    temp.push_back(make_pair(make_pair(st, en), s));
    exists.insert(mak(H1(s), H2(s)));
    reverse(s.begin(), s.end());
    exists.insert(mak(H1(s), H2(s)));
  }
  g();
  for (auto it : temp) {
    O(query(it.first.first, it.first.second, it.second));
  }
  return 0;
}

```