An industrial system contains $n$ devices, labeled $1 \sim n$. These devices are connected by $n-1$ bidirectional conveyors, forming an unrooted tree.

When using this system, one must first designate a device $x$ ($1 \le x \le n$) as the final device, and then set the direction of all conveyors to point towards this device. Formally, device $x$ is designated as the root, and all conveyor directions are set to point towards the root, forming an inward-rooted tree. Once the directions of all conveyors are determined, all products will be transported along the direction of the conveyors.

Each device receives products from all its descendants as input, then produces a new product and outputs it along the conveyor to all its ancestors. Formally, let the product of device $y$ ($1 \le y \le n$) be $a_{x,y}$. If the devices in its subtree (excluding the device itself) are $z_1, \dots, z_k$, then its product can be represented as the multiset $a_{x,y} = \{a_{x,z_1}, \dots, a_{x,z_k}\}$. Specifically, if device $y$ is a leaf device, i.e., device $y$ has no descendants, then $a_{x,y} = \emptyset$.

To facilitate the comparison of product quality, the size relationship of products can be defined recursively as follows: when device $x$ ($1 \le x \le n$) is designated as the final device, for products $a_{x,y}$ and $a_{x,z}$ of devices $y, z$ ($1 \le y, z \le n$), the dictionary order relationship of the two sequences obtained by sorting all elements in $a_{x,y}$ and $a_{x,z}$ (i.e., all input products of devices $y$ and $z$) from largest to smallest is the size relationship of $a_{x,y}$ and $a_{x,z}$. Formally, let $a_{x,y} = \{b_1, b_2, \dots, b_p\}$ and $a_{x,z} = \{c_1, c_2, \dots, c_q\}$, where $b_1 \ge b_2 \ge \dots \ge b_p$ and $c_1 \ge c_2 \ge \dots \ge c_q$, then:

• $a_{x,y} > a_{x,z}$ if and only if one of the following two conditions is met:
  • There exists a positive integer $i \in [1, \min(p, q)]$ such that $b_i > c_i$, and for all $1 \le j < i$, $b_j = c_j$;
  • For all $1 \le i \le \min(p, q)$, $b_i = c_i$, and $p > q$;
• $a_{x,y} = a_{x,z}$ if and only if $p = q$ and for all $1 \le i \le p$, $b_i = c_i$.

After defining the size relationship of products, the ranking of products can be defined. Specifically, define $f(x, y)$ ($1 \le x, y \le n$) as: when device $x$ is designated as the final device, the rank of device $y$'s product $a_{x,y}$ among all $n$ products. Formally, $$f(x, y) = 1 + \sum_{z=1}^{n} [a_{x,z} > a_{x,y}]$$

To comprehensively analyze the role of each device in this industrial system, you need to answer $m$ queries. The form of a query is as follows:

• Given five parameters $s, t, o_x, o_y, r$;
• Define $$X = \begin{cases} \{s\}, & o_x = 0 \\ \text{ch}(s, t), & o_x = 1 \end{cases}, \quad Y = \begin{cases} \{t\}, & o_y = 0 \\ \text{ch}(s, t), & o_y = 1 \end{cases}$$
• Where $\text{ch}(s, t)$ denotes the set of all devices on the simple path from device $s$ to device $t$;
• Find the number of pairs $(x, y)$ such that $x \in X$, $y \in Y$ and $f(x, y) \le r$.

Input

Read data from the file industry.in. The first line contains a non-negative integer $c$, representing the test point number. $c = 0$ indicates that this test point is a sample. The second line contains a positive integer $n$, representing the number of devices in the industrial system. The $i+2$-th line ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$, representing the numbers of the two devices connected by the $i$-th conveyor. The $n+2$-th line contains a positive integer $m$, representing the number of queries. The $i+n+2$-th line ($1 \le i \le m$) contains five non-negative integers $s, t, o_x, o_y, r$, representing the parameters given for the $i$-th query.

Output

Output to the file industry.out. Output $m$ lines, where the $i$-th line ($1 \le i \le m$) contains a non-negative integer, representing the answer to the $i$-th query.

Constraints

Examples

Input 1

0
3
1 2
2 3
6
1 2 0 0 2
1 3 0 0 2
2 3 0 0 2
2 1 0 0 2
3 1 0 0 2
3 2 0 0 2

Output 1

1
0
1
1
0
1

Input 2

(industry2.in)

Output 2

(industry2.ans)

Input 3

(industry3.in)

Output 3

(industry3.ans)

Input 4

(industry4.in)

Output 4

(industry4.ans)

Input 5

(industry5.in)

Output 5

(industry5.ans)

Input 6

(industry6.in)

Output 6

(industry6.ans)

Input 7

(industry7.in)

Output 7

(industry7.ans)

Input 8

(industry8.in)

Output 8

(industry8.ans)

Input 9

(industry9.in)

Output 9

(industry9.ans)

Input 10

(industry10.in)

Output 10

(industry10.ans)

Input 11

(industry11.in)

Output 11

(industry11.ans)

Input 12

(industry12.in)

Output 12

(industry12.ans)

Input 13

(industry13.in)

Output 13

(industry13.ans)

Input 14

(industry14.in)

Output 14

(industry14.ans)

Input 15

(industry15.in)

Output 15

(industry15.ans)

Input 16

(industry16.in)

Output 16

(industry16.ans)

Input 17

(industry17.in)

Output 17

(industry17.ans)

Input 18

(industry18.in)

Output 18

(industry18.ans)

Input 19

(industry19.in)

Output 19

(industry19.ans)

Special Properties

• Special Property A: There exists $1 \le x \le n$ such that for all $1 \le i \le n-1$, $u_i = x$ or $v_i = x$.
• Special Property B: The unrooted tree formed by all devices is generated uniformly at random among all labeled unrooted trees with $n$ nodes.