You will be given a weighted rooted tree, where root is node 1. For each subtree of that tree, you will have to compute the summation of lengths of all possible simple paths present in that subtree. Eventually you need to print the summation of those values modulo 1000000007.

Image of the tree in the first sample is given below.

Input

First line of input will contain an integer T (1 <= T <= 10) denoting the number of test cases. Each test case will begin with an integer N (1 <= N <= 100000), indicating number of nodes. The following N-1 lines will have three integers each, U (1 <= U <= N), V (1 <= V <= N), W (1 <= W <= 1000000000), which denotes that there is an edge in the tree from node U to node V having W weight.

Input File is large. Use fast I/O methods.

Output

For each test case, print the case number then print the answer to the problem modulo 1000000007 in separate lines.

Example

Input:
2
7
1 2 3
1 3 2
2 4 1
2 5 4
3 6 6
3 7 8
6
1 2 3
1 3 2
1 4 4
3 5 7
3 6 1

Output:
Case 1: 212
Case 2: 109

Explanation of Sample

Explanation of the 1^st sample: Summation of lengths of all possible sample paths for each subtree is given below:

• 1: 174
• 2: 10
• 3: 28
• 4: 0
• 5: 0
• 6: 0
• 7: 0

Explanation of the 2^nd sample: Summation of lengths of all possible sample paths for each subtree is given below:

• 1: 93
• 2: 0
• 3: 16
• 4: 0
• 5: 0
• 6: 0