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.