Background

Mengmeng bought a seed of a string tree. If she plants it in spring, by summer it will grow into a huge string tree. The string tree is very special: its branches are densely covered with strings, and it looks very complicated.

Problem Description

A string tree is essentially still a tree, i.e., a connected undirected acyclic graph with $N$ nodes and $N-1$ edges, where nodes are numbered from $1$ to $N$. Different from an ordinary tree, each edge in the tree corresponds to a string.

When Mengmeng and JYY are playing under the tree, Mengmeng decides to test JYY. Each time, Mengmeng writes down a string $S$ and two nodes $U, V$. JYY needs to immediately answer: on the shortest path between $U$ and $V$ (i.e., the path with the fewest edges; since it is a tree, this path is unique), how many edge strings have $S$ as a prefix.

Although JYY is good at programming, he is not good at string processing. So he asks you to help solve Mengmeng's problem.

Input Format

The first line contains an integer $N$, representing the number of nodes in the string tree.

The next $N-1$ lines each contain two integers $U, V$, followed by a string $S$, meaning there is an edge directly connecting node $U$ and node $V$, and the string on this edge is $S$. The input guarantees that the given graph is a valid tree.

The next line contains an integer $Q$, representing the number of questions from Mengmeng.

The next $Q$ lines each contain two integers $U, V$, followed by a string $S$, meaning the question asks: on the shortest path between node $U$ and node $V$, how many edge strings have $S$ as a prefix.

Output Format

Output $Q$ lines. Each line should contain the answer to the corresponding question.

4
1 2 ab
2 4 ac
1 3 bc
3
1 4 a
3 4 b
3 2 ab

2
1
1

Hint

For $100\%$ of the testdata, $1 \leq N, Q \leq 10^5$. The total length of all input strings does not exceed $10$, and all strings contain only lowercase letters a~z.

Translated by ChatGPT 5