H

Save the Trees

N trees were planted on a side of a long straight road. In the other side there are farms, industries etc. The market price of these trees is huge now. Some greedy people want to cut these trees down and want to be millionaires. They got the permission from the Govt. decoying that they would develop the area. You published this fact in the web and millions raised their voices against this conspiracy.

You gathered the information of the trees and found the type and height of all trees. For simplicity, you represented them as integers. You want to find the overall price of the trees. To find the price, the following method is used.

1)      The trees are first partitioned into groups with the condition that, types of two trees will not be similar in a group. A group can only be formed using contiguous trees.

2)      The price of a group is equal to the height of the tallest tree.

3)      The overall price is the summation of prices of all groups.

Now you want to find the minimum possible price of the trees in this scheme and show the Govt. that even though you calculated the minimum possible price, it's actually huge.

Input

The first line of input will contain T (≤ 12) denoting the number of cases.

Each case starts with and integer N (1 ≤ N ≤ 105). Each of the next N lines contains two integers typei heighti (1 ≤ typei ≤ 105, 1 ≤ heighti ≤ 20000) of the ith tree from left to right.

Output

For each case, print the case number and the minimum possible price of the trees according to the scheme described above.

Sample Input

Output for Sample Input

 
1
5
3 11
2 13
1 12
2 9
3 13
 
Case 1: 26

Note

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan, Special Thanks: Md. Mahbubul Hasan, Md. Arifuzzaman Arif