You are organizing a wrestling tournament. The tournament will be a playoff tournament, where 2N wrestlers meet in N rounds. In each round, the re- maining wrestlers are paired up and pitted against each other. The winning wrestlers then proceed to the next round, and the losing wrestlers are out of the tournament. After the N-th round, one lucky champion remains. Exactly who meets who in each round is decided randomly. Officially, that is. Unofficially, however, your number one priority is of course to make all the matches as entertaining as possible. You therefore try to make sure that the matches are scheduled in such a way that the least exciting match will be as exciting as possible. To be able to quantify this, you have assigned an Index of Certainly Perceived Charm to each pair of wrestlers. The higher the ICPC, the more excit- ing you anticipate that a match between those two wrestlers will be. Write a program to determine the ICPC of the least exciting match in the current round, provided we schedule the round in such a way so as to make this as large as possible. Input The first line of input contains an integer T, giving the number of test cases. Each test case, giving a round to be scheduled, begins with an integer 1 ≤ N ≤ 6, indicating that there are W = 2N wrestlers in the round. Then follow W − 1 lines of integers, the i:th of which contains W − i integers. The j-th integer on the i-th line gives the ICPC of wrestlers i and i + j. The ICPC’s are integers between 1 and 109, inclusive. Output For each test case, output a line ‘Case X: Y ’, where X is the number of the test case (starting from 1), and Y is the ICPC of the least exciting match, provided an optimal schedule is used. Sample Input 2 2 100 100 100 100 100 100 2
2/2 300 300 300 100 200 100 Sample Output Case 1: 100 Case 2: 200