Given an industrial system containing $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

For all test data: $2 \le n \le 10^5$; For all $1 \le i \le n-1$, $1 \le u_i, v_i \le n$, and $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ form a tree; $1 \le m \le 10^5$; $1 \le s, t, r \le n$, $o_x, o_y \in \{0, 1\}$.

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.

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

Note 1

• When device 1 is the root:
  • Device 3 is a leaf device, so $a_{1,3} = \emptyset$;
  • All descendants of device 2 are device 3, so $a_{1,2} = \{\emptyset\}$;
  • All descendants of device 1 are devices 2, 3, so $a_{1,1} = \{\{\emptyset\}, \emptyset\}$;
  • Therefore $a_{1,1} > a_{1,2} > a_{1,3}$, i.e., $f(1, 1) = 1$, $f(1, 2) = 2$, $f(1, 3) = 3$.
• When device 2 is the root:
  • Devices 1, 3 are leaf devices, so $a_{2,1} = a_{2,3} = \emptyset$;
  • All descendants of device 2 are devices 1, 3, so $a_{2,2} = \{\emptyset, \emptyset\}$;
  • Therefore $a_{2,2} > a_{2,1} = a_{2,3}$, i.e., $f(2, 2) = 1$, $f(2, 1) = f(2, 3) = 2$.
• When device 3 is the root:
  • Device 1 is a leaf device, so $a_{3,1} = \emptyset$;
  • All descendants of device 2 are device 1, so $a_{3,2} = \{\emptyset\}$;
  • All descendants of device 3 are devices 1, 2, so $a_{3,3} = \{\{\emptyset\}, \emptyset\}$;
  • Therefore $a_{3,3} > a_{3,2} > a_{3,1}$, i.e., $f(3, 3) = 1$, $f(3, 2) = 2$, $f(3, 1) = 3$.