You and your friend are studying a tree containing $n$ nodes. This is a rooted tree with node $1$ as the root. The depth $\text{dep}_u$ of each node $u$ is defined as the number of nodes on the simple path from $u$ to the root. Additionally, define $\text{LCA}^*(l, r)$ as the lowest common ancestor of the nodes with indices in the range $[l, r]$, i.e., the node with the maximum depth among all common ancestors of nodes $l, l+1, \dots, r$. You are given $q$ queries. In each query, you are given three parameters $l, r, k$, and you need to find the maximum depth of the lowest common ancestor among all contiguous sub-segments of $[l, r]$ with length at least $k$. That is: $$\max_{l \le l' \le r' \le r \land r' - l' + 1 \ge k} \text{dep}_{\text{LCA}^*(l', r')}$$ Your task is to help answer these queries.

Input

The first line contains a positive integer $n$, representing the number of nodes in the tree. The next $n-1$ lines each contain two positive integers $u, v$, representing an edge between node $u$ and node $v$. The next line contains a positive integer $q$, representing the number of queries. The next $q$ lines each contain three positive integers $l, r, k$, describing a query.

Output

For each query, output a single line containing one integer, representing the corresponding answer.

Examples

Input 1

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

Output 1

3
4
3

Note 1

Figure 3: The tree in Example 1

• For the first query, $\text{LCA}^*(2, 3) = 2$, $\text{LCA}^*(3, 4) = 2$, $\text{LCA}^*(4, 5) = 6$. The depth of $2$ is $3$, and the depth of $6$ is $2$, so the answer is $\max\{3, 3, 2\} = 3$.
• For the second query, the answer is the maximum depth of nodes $1, 2, 3, 4$, so the answer is $4$.
• For the third query, $\text{LCA}^*(1, 3) = 1$, $\text{LCA}^*(2, 4) = 2$, $\text{LCA}^*(3, 5) = 6$, $\text{LCA}^*(4, 6) = 6$. The maximum depth is $2$, so the answer is $3$.

Examples 2, 3, 4

See the files query/query2.in and query/query2.ans, query/query3.in and query/query3.ans, and query/query4.in and query/query4.ans in the contestant's directory.

Constraints

For all test cases, it is guaranteed that: $1 \le n, q \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le k \le r - l + 1$.

Property A: The input tree is a chain, and the degree of the root is $1$. Property B: For each query, $k = r - l + 1$.