Problem Description

Charles is a truck driver in the city of Googleland. Googleland is built in the form of a tree with $N$ nodes, where each node represents a city and each edge represents a road between $2$ cities. The cities are numbered $1$ to $N$. The capital of Googleland is city $1$. Each day Charles picks up a load of weight $W$ in city $C$ and wants to deliver it to city $1$ using the simple path (which is unique) between the cities. Each road $i$ has a toll which charges amount $A_i$ if the weight of the load is greater than or equal to a load-limit $L_i$.

Charles works for $Q$ days, where for each day Charles will be given the starting city $C$ and weight of the load $W$. For each day, find the greatest common divisor of all the toll charges that Charles pays for that day. If Charles did not have to pay in any of the tolls, the answer is $0$.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains the $2$ integers $N$ and $Q$.

The next $N - 1$ lines describe the roads. The $i$-th of these lines contains the $4$ space-separated integers $X$, $Y$, $L_i$ and $A_i$, indicating a road between cities $X$ and $Y$ with load-limit $L_i$ and toll charge $A_i$.

The next $Q$ lines describe the queries. The $j$-th of these lines contains the $2$ space-separated integers $C_j$ and $W_j$ representing the starting city and weight of the load on the $j$-th day.

Output Format

For each test case, output $1$ line containing Case #$x$: followed by $y$, where $x$ is the test case number (starting from $1$) and $y$ is a list of the answers for $Q$ days in order, separated by spaces.

2
7 5
2 1 2 4
2 3 7 8
3 4 6 2
5 3 9 9
2 6 1 5
7 1 5 7
5 10
5 8
4 1
6 1
7 6
3 2
1 2 2 10
3 2 3 5
3 2
3 3

Case #1: 1 4 0 5 7
Case #2: 10 5

Hint

In Sample Case #$1$

On the first day, Charles should pay toll charges in the roads between cities $(5, 3)$, $(3, 2)$ and $(2, 1)$. The answer will be $\gcd(9, 8, 4) = 1$.

On the second day, Charles should pay toll charges in the roads between cities $(3, 2)$ and $(2, 1)$. The answer will be $\gcd(8, 4) = 4$.

On the third day, Charles need not pay toll charges in any of the cities. Thus, the answer will be $0$.

In Sample Case #$2$

On the first day, Charles should pay toll charges in the roads between cities $(2, 1)$. The answer will be $10$.

On the second day, Charles should pay toll charges in the roads between cities $(3, 2)$ and $(2, 1)$. The answer will be $\gcd(5, 10) = 5$.

Limits

$1 \le T \le 100$.

$1 \le L_i \le 2 \times 10^5$, for all $i$.

$1 \le A_i \le 10^{18}$, for all $i$.

All $L_i$ are distinct.

$2 \le C_j \le N$, for all $j$.

$1 \le W_j \le 2 \times 10^5$, for all $j$.

It is guaranteed that given roads form a tree.

Test Set $1$

$2 \le N \le 1000$.

$1 \le Q \le 1000$.

Test Set $2$

$2 \le N \le 5 \times 10^4$ and $1 \le Q \le 10^5$ for at most $20$ test cases.

For the remaining cases, $2 \le N \le 1000$ and $1 \le Q \le 1000$.