Now we got a map of their road system. We want to know that, for some pair of cities U and V, how much tax one had to pay for going to city U to V in the cheapest path (Cheapest in terms of taxes).

**INPUT**

First line of the input is the test case number $T (T <= 5)$. Then T test cases follow. Each case

starts with two integers $ N (1 <= N <= 20000) $ and $Q (1 <= Q <= 20000) $. $N$ is the number of

city of the road system. $Q$ is the number of pair of cities for which you need to calculate the

tax. In next $N-1$ lines, there will be $3$ integer numbers $U, V$ and $W (1 <= U, V <= N$ and $0 <= W

<= 1000000)$. This means there was a road from city $ U$ to city $V $ and if anybody wants to go

to only from $U$ to $ V$ or $V$ to $ U$, he/she has to give $W$ tax. Or if they are going to any other

cities and they cross this road, the cost needed will be XORed with W. Then Q lines follow ; in

each line there will be$ 2$ integer numbers $U$ and $V$. $ (1 <= U, V <= N)$

**OUTPUT**

For each test case first print $"Case$ $C:"$ where $C$ is the test case number. Then $Q$ lines follow;

each line consists of a single number, minimum tax needed for going from city $U$ to city $V$ in

cheapest path.

**SAMPLE INPUT**

**SAMPLE OUTPUT**