In the year 545 of the Tower Calendar, the Tower Kingdom held the 510th election for its king.

The Tower Kingdom consists of $n$ cities connected by $n-1$ roads, forming a tree structure of size $n$. Cheng Liangzhou was successfully elected, which caused dissatisfaction among some local regimes.

Consequently, in the year 546 of the Tower Calendar, $q$ revolutions broke out in the Tower Kingdom. The $i$-th revolution was initiated by all cities along the simple path from $x_i$ to $y_i$.

However, the Tower Kingdom's army was well-trained. For the $i$-th revolution, the revolutionary army was suppressed after advancing a distance of $d_i$.

As the historian of the Tower Kingdom, you are tasked with recording these $q$ revolutions and calculating how many cities were affected by each revolution.

Problem Description

Given a tree of size $n$.

Let $x \to y$ denote the simple path between $x$ and $y$ in the tree. The distance $\operatorname{dis}(x, y)$ between two nodes $x$ and $y$ is defined as the number of edges on the simple path between them.

The distance from a node $u$ to a simple path $x \to y$ is defined as $\min_{v \in x \to y} \operatorname{dis}(u, v)$.

There are $q$ queries. Each query $i$ provides three integers $x_i, y_i, d_i$, where $1 \le x_i, y_i \le n$ and $0 \le d_i < n$. You need to calculate the number of nodes whose distance to the path $x_i \to y_i$ is less than or equal to $d_i$.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $u_i, v_i$, representing an edge in the tree.

The $(n+1)$-th line contains an integer $q$.

The next $q$ lines each contain three integers $x_i, y_i, d_i$, describing a query.

Output

Output $q$ lines, each containing an integer representing the answer to the $i$-th query.

Constraints

For all data, $1 \le n, q \le 2 \times 10^5$.

• Subtask 1 (7 points): $n, q \le 5000$.
• Subtask 2 (8 points): $x_i = y_i$.
• Subtask 3 (23 points): The path $x_i \to y_i$ contains at most $20$ nodes.
• Subtask 4 (22 points): $d_i \le 20$.
• Subtask 5 (20 points): $n, q \le 5 \times 10^4$.
• Subtask 6 (20 points): No special restrictions.

Examples

Input 1

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

Output 1

5
1
4