bee 1782 - Honorable Gift

Guga won a connected graph for his birthday, with N nodes and N-1 bidirectional edges. Each edge has a weight and connects two nodes. When Andre found out about Guga’s gift, he came up with the following game: Given an integer X, how many pairs (A,B) (A ≤ B) exist such that all edges of the shortest path from node A to node B have weight less than or equal to X?

Now Guga and Andre need a program to answer a lot of these questions, so they can play indefinitely and know whether they got the right answer.

Input

The first line of input contains an integer T (1 ≤ T ≤ 50), the number of test cases. The first line of each test case contains N (1 ≤ N ≤ 10⁵), the number of nodes in Guga’s graph. Each of the following N-1 lines contains three integers A (1 ≤ A ≤ N), B (1 ≤ B ≤ N) and C (1 ≤ C ≤ 10⁶), indicating that there is an edge from node A to node B with weight C. The next line contains an integer Q (1 ≤ Q ≤ 10⁴), the number of times that Guga and Andre will play. The following line contains Q integers X_i (1 ≤ X_i≤ 10⁶), the greatest weight allowed in the shortest path, as explained above.

Output

For each test case print “Caso #X:”, where X is the number of the current case, starting at 1, followed by the answers for each of the Q queries of this test case preceded by a single space.

Input Sample	Output Sample
3 3 1 2 2 1 3 2 2 1 2 4 1 2 3 2 3 5 3 4 7 1 6 1 2 1 10	Caso #1: 3 6 Caso #2: 7 Caso #3: 1 1