This is year 2050 and your school is hosting IOI 2050 this time. To organize the contest a lot of LAN cables will be laid down. N students from different countries will be coming to earn the prize of IOI winner. You are being asked to come up with a plan such that LAN utilization is minimized and all computers are connected to each other diretly or undirectly. LAN will be laid to connect these N computers. You will be given information about which computer to be connected to which and distance between them.
After you have come up with a plan you will be asked M queries of the form $u,v$ for which you have to tell the minimum length of LAN used connect computers u and v according to your plan.

[Input]
First line contains a single integer t, denoting number of test cases.
Each test case begins with a line containing 3 integers $N,P,M$ denoting number of students, number of connections and number of queries respectively.
Next p line contains 3 integers $u,v,d$ each denoting computer u and computer v and d denoting distance between them.
Next M line contains 2 integers $u,v$ each denoting computer u and v.

[Output]
For each test case print "Case: case_no" followed by m queries solution.
For each query output the minimum length of cable used to connect u and v.

[Constraints]
$1<=t<=50$
$1<=N<=1000$
$N-1<=P<=100000$
$1<=M<=100000$
$1<=u,v<=N$
$1<=d<=1000000$
Within each test case d for each connection will be unique.

NOTE: Use scanf/printf. Large Input data.