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 defences 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