In 2202, the Coronavirus pandemic sweeps the country Y again. As a researcher in country Y, Dr. W hopes to find a way to fight the virus.

Dr. W has an experiment equipment, which consists of $n$ nodes and $n-1$ bidirectional pipes, the $i$-th pipe connects $u_i$, $v_i$. Any pair of nodes can reach each other through the pipe. Dr. W has four kinds of operating devices, which can perform one of the four operations of ${\tt abcd}$ respectively. On each pipe, there is exactly one kind of operation that can be performed by the operating device. The operating device on the $i$-th pipe performs $c_i$ operation on the virus.

Dr. W will do experiments for $q$ times. In the $i$-th experiment, two nodes $s_i$, $t_i$ will be selected, and then Dr. W will put the virus into the node numbered $s_i$, let it reach the node numbered $t_i$ through the shortest path, and then take it out. Virus will be operated by the operating devices on the shortest path one by one.

Dr. W found that if a certain operation sequence is the same as the reverse of it, the virus may mutate uncontrollably after this operation. For example, a virus operated by ${\tt a}$, ${\tt abba}$ or ${\tt cabac}$ is uncontrollable, while a virus operated by ${\tt ab}$ or ${\tt bba}$ are not. In particular, the initial virus without any operation is controllable.

In an experiment, if the virus is uncontrollable when it reaches a certain node $u$, the node $u$ is said to be dangerous. {\bf The risk level} of an experiment is defined as the number of dangerous nodes on the path.

In order to estimate the risk of the experiments, Dr. W wants you to tell him {\bf the risk level} of each experiment.

Input

The first line contains two integers $n$ and $q$.

Next $n-1$ lines, each with two integers $u_i,v_i$ and a character $c_i$.

Next $q$ lines, each with two integers $s_i$ and $t_i$.

Output

$q$ lines, each with an integer representing the risk level of an experiment.

Example

Input 1

7 5
1 2 a
2 3 a
3 4 a
2 5 b
1 6 b
6 7 a
2 7
4 7
3 6
6 3
4 1

Output 1

2
3
2
1
3

Explanation 1

The total operation sequences of the five experiments are: ${\tt aba}, {\tt aaaba}, {\tt aab}, {\tt baa}, {\tt aaa}$.

Take the first experiment as an example:

After reaching the node $1$, the operation sequence is ${\tt a}$, and after reaching the node $7$, the operation sequence is ${\tt aba}$. These two operation sequences are the same as the reverse, so node $1$ and node $7$ are dangerous.

After reaching the node $2$, the operation sequence is ${\tt ab}$, and the reverse is ${\tt ba}$, which is different from the original sequence, so it is not dangerous.

There are a total of $2$ nodes that are dangerous, so {\bf the risk level} for this experiment is $2$.

Input 2

12 12
1 2 a
2 3 b
3 4 a
4 5 b
5 6 b
6 7 a
7 8 b
8 9 a
9 10 b
10 11 a
11 12 b
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 12
11 12
12 12

Output 2

3
3
2
2
4
3
3
2
2
1
1
0

Subtasks

Subtask 1 (5pts): $n,q \le 100$.

Subtask 2 (12pts): $n,q \le 2000$.

Subtask 3 (21pts): $n,q \le 40000$.

Subtask 4 (17pts): The tree is guaranteed to be a chain.

Subtask 5 (45pts): No special properties.

For $100\%$ data, $1\leq n,q\leq 10^5$, $1\leq u_i,v_i,s_i,t_i\leq n,c_i\in\{{\tt a},{\tt b},{\tt c},{\tt d}\}$.