Brandon likes to go up and down. Brandon has a tree rooted at vertex ~1~. The root is at depth zero, and the depth of any non-root node is one more than the depth of its parent. Therefore, all node depths are nonnegative.

Brandon wants to know, for ordered pairs of positive integers ~(a, b)~, how many ordered pairs of vertices ~(u, v)~ have a shortest path that involves going up the rooted tree by exactly ~a~ vertices and then going down the rooted tree by exactly ~b~ vertices. When going up the tree, the depth of vertices decreases. When going down the tree, the depth of vertices increases.

Constraints

~3 \le N \le 10^4~

~1 \le Q \le 10^5~

~1 \le u_i, v_i \le N~

~1 \le a_i, b_i < N~

~a_i + b_i < N~

No ~(a_i, b_i)~ pair will appear more than once.

Input Specification

Each test case starts with a line containing a single positive integer, ~N~. The next ~N-1~ lines contain two positive integers, ~u_i~ and ~v_i~, indicating those two vertices are connected by an edge. It is guaranteed that the provided graph is a tree.

After that, a line containing a single positive integer, ~Q~, is given. The next ~Q~ lines contain two positive integers, ~a_i~ and ~b_i~, representing a query. Brandon wishes to count the number of ordered pairs of vertices that have a shortest path that involves going up the rooted tree by ~a~ vertices and then going down the rooted tree by ~b~ vertices.

Output Specification

Output ~Q~ lines in order, the answers to the given ~Q~ queries.

Sample Input

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

Sample Output

1
1
0