#216829. [GKS 2021 #B] Truck Delivery

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

Charles works for days, where for each day Charles will be given the starting city and weight of the load . 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 .

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

The first line of each test case contains the integers and .

The next lines describe the roads. The -th of these lines contains the space-separated integers , , and , indicating a road between cities and with load-limit and toll charge .

The next lines describe the queries. The -th of these lines contains the space-separated integers and representing the starting city and weight of the load on the -th day.

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

样例输入 1

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

样例输出 1

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

In Sample Case #

On the first day, Charles should pay toll charges in the roads between cities , and . The answer will be .

On the second day, Charles should pay toll charges in the roads between cities and . The answer will be .

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

In Sample Case #

On the first day, Charles should pay toll charges in the roads between cities . The answer will be .

On the second day, Charles should pay toll charges in the roads between cities and . The answer will be .

Limits

.

, for all .

, for all .

All are distinct.

, for all .

, for all .

It is guaranteed that given roads form a tree.

Test Set

.

.

Test Set

and for at most test cases.

For the remaining cases, and .