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.
~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.
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 ~Q~ lines in order, the answers to the given ~Q~ queries.
5 5 2 1 5 5 3 3 4 3 1 2 2 1 2 2
1 1 0