Little W has a tree with $n$ nodes, where each edge in the tree can be either a light edge or a heavy edge. You need to perform $m$ operations on the tree. Before all operations begin, all edges in the tree are light edges. There are two types of operations:

1. Given two nodes $a$ and $b$, first, for all nodes $x$ on the path from $a$ to $b$ (including $a$ and $b$), you must change all edges connected to $x$ to light edges. Then, change all edges contained on the path from $a$ to $b$ to heavy edges.
2. Given two nodes $a$ and $b$, you need to calculate how many heavy edges are currently on the path from $a$ to $b$.

Input

There are multiple test cases. The first line of the input contains a positive integer $T$, representing the number of test cases. For each test case:

The first line contains two integers $n$ and $m$, where $n$ is the number of nodes and $m$ is the number of operations. The next $n - 1$ lines each contain two integers $u$ and $v$, representing an edge in the tree. The next $m$ lines each contain three integers $op_i, a_i, b_i$, describing an operation, where $op_i = 1$ denotes a type 1 operation and $op_i = 2$ denotes a type 2 operation.

It is guaranteed that $a_i \neq b_i$.

Output

For each type 2 operation, output one integer per line representing the answer.

Examples

Input 1

1
7 7
1 2
1 3
3 4
3 5
3 6
6 7
1 1 7
2 1 4
2 2 7
1 1 5
2 2 7
1 2 1
2 1 7

Output 1

1
3
2
1

Note

Explanation for Example 1: After the 1st operation, the heavy edges are: $(1, 3), (3, 6), (6, 7)$. For the 2nd operation, the heavy edges included are: $(1, 3)$. For the 3rd operation, the heavy edges included are: $(1, 3), (3, 6), (6, 7)$. For the 4th operation, first $(1, 3)$ and $(3, 6)$ become light edges, then $(1, 3)$ and $(3, 5)$ become heavy edges. For the 5th operation, the heavy edges included are: $(1, 3), (6, 7)$. For the 6th operation, first $(1, 3)$ becomes a light edge, then $(1, 2)$ becomes a heavy edge. For the 7th operation, the heavy edges included are: $(6, 7)$.

Input 2

See edge/edge2.in in the contestant directory.

Output 2

See edge/edge2.ans in the contestant directory.

Note

The constraints for this example are consistent with test cases 3 ~ 6.

Input 3

See edge/edge3.in in the contestant directory.

Output 3

See edge/edge3.ans in the contestant directory.

Note

The constraints for this example are consistent with test cases 9 ~ 10.

Input 4

See edge/edge4.in in the contestant directory.

Output 4

See edge/edge4.ans in the contestant directory.

Note

The constraints for this example are consistent with test cases 11 ~ 14.

Input 5

See edge/edge5.in in the contestant directory.

Output 5

See edge/edge5.ans in the contestant directory.

Note

The constraints for this example are consistent with test cases 17 ~ 20.

Constraints

For all test data: $T \leq 3$, $1 \leq n, m \leq 10^5$.

Special Property A: The tree is a chain. Special Property B: The nodes $a_i$ and $b_i$ given in type 2 operations are directly connected by an edge.