Terrorists! There are terrorists everywhere!!! I was shouting out loud after I had watched a few news
reports about terrorism acts that had happened around my neighborhoods. I started to think that hiding at
home wasn’t a good way to go.
I went to police stations and asked around if I could help them prevent these issues. The police
gave me pieces of information about terrorists’ plans. I ended up lying on my bed and figuring way to
utilize this information. That is why I come to you.
Our neighborhoods could be illustrated with intersections and roads. Terrorists usually meet up at
one intersection before moving to another intersection to perform an illegal act. The given information
tells us where they will meet and where they will go. Unfortunately, the certain schedules of those plans
are not available and too few policemen are available lately. So, the police will not be able to set up
efficient defenses to all of those acts. What they could do is set up surveillance cameras to all meet up
intersections. Once a meet up is detected, policemen will go to that meet up’s destination to catch the
terrorists. The policemen rarely accomplish it because they spend too long time travelling between places.
Because terrorists are smart, they always use shortest route to travel between intersections.
Because the policemen aren’t that smart, they need our help. For each terrorist plan, the police want us to
compute the shortest distance between the meet up place and the destination. If the distance is too short,
they will not spend their efforts for free.
Input
The first line of the input contains an integer T, the number of test sets (1 <= T <= 5).
Each test case consists of many lines. The first line contains 3 integers N, M, Q which are the
number of intersections, the number of roads, and the number of terrorists’ plans in respective order.
1 <= N <= 100 000, N - 1 <= M <= N + 50, 1 <= Q <= 50 000
Then the next M lines describe the roads in our neighborhoods. A road is described by 3
integers: U, V, D. Ui and Vi represent 2 ends of the road i. Di represents distance of that road.
1 <= Ui, Vi <= N, 1 <= Di <= 10 000. It is possible that many roads might exist between a pair of
intersection.
Finally the next Q lines are the terrorism plans. A plan j is described by 2 integers: Sj and Ej
which are the meet-up intersection and the destination intersection respectively. 1 <= Sj, Ej <= N.
Output
For each test set, print out “Case x:” where x is a case number beginning with 1, and then
followed by Q lines. For each terrorism plan, output the shortest distance between the meet-up
intersection and the destination of the plan.

Example

Input:
1
7 9 5
7 6 6114
5 3 5473
2 4 2601
5 4 8525
7 3 291
2 7 3363
1 6 399
6 4 4477
1 7 3075
6 3
4 4
3 1
2 3
7 3
Output:
Case 1:
3765
0
3366
3654
291