Given a tree with $n$ vertices rooted at vertex $1$. While walking through it with her cat Chefir, Sakurako got distracted, and Chefir ran away.

To help Sakurako, Kosuke recorded his $q$ guesses. In the $i$-th guess, he assumes that Chefir got lost at vertex $v_i$ and had $k_i$ stamina.

Also, for each guess, Kosuke assumes that Chefir could move along the edges an arbitrary number of times:

• from vertex $a$ to vertex $b$, if $a$ is an ancestor$^{\text{∗}}$ of $b$, the stamina will not change;
• from vertex $a$ to vertex $b$, if $a$ is not an ancestor of $b$, then Chefir's stamina decreases by $1$.

If Chefir's stamina is $0$, he cannot make a move of the second type.

For each assumption, your task is to find the distance to the farthest vertex that Chefir could reach from vertex $v_i$, having $k_i$ stamina.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

Each test case is described as follows:

• The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
• The next $n-1$ lines contain the edges of the tree. It is guaranteed that the given edges form a tree.
• The next line consists of a single integer $q$ $(1\le q\le 2 \cdot 10^5)$, which denotes the number of guesses made by Kosuke.
• The next $q$ lines describe the guesses made by Kosuke, with two integers $v_i$, $k_i$ $(1\le v_i \le n, 0 \le k_i\le n)$.

It is guaranteed that the sum of $n$ and the sum of $q$ across all test cases does not exceed $2\cdot 10^5$.

Output

For each test case and for each guess, output the maximum distance to the farthest vertex that Chefir could reach from the starting point $v_i$ having $k_i$ stamina.

见题面 Input 部分

见题面 Output 部分

In the first example:

• In the first query, you can go from vertex $5$ to vertex $3$ (after which your stamina will decrease by $1$ and become $0$), and then you can go to vertex $4$;
• In the second query, from vertex $3$ with $1$ stamina, you can only reach vertices $2$, $3$, $4$, and $5$;
• In the third query, from vertex $2$ with $0$ stamina, you can only reach vertices $2$, $3$, $4$, and $5$;