The battle of Hogwarts is going to start very soon. Hermione has received some very important information about the death eaters. They have invented a new way to increase their power using their wands. Each death eater can carry two wands, one in the left hand and other in the right hand. They will stand in a line and create the front of their army. Hermione knows the order of the death eaters in the line and the value of their strength. For death eaters, the value of strength and power may be different. The value of power of each death eater is initially 1. They can use both of their wands to increase power. One can use his/her left hand’s wand to connect to another death eater’s left hand whose strength is strictly less than connector’s strength and also in the left side of the connector. Same is true for right hand i.e. one can use his/her right hand’s wand to connect to another death eater’s right hand whose strength is strictly less than connector’s strength and also in the right side of the connector. In this way, s/he can create a sequence where the strength increases from the leftmost person, becomes highest at his/her position and decreases on the right side. The power is equal to the length of this sequence and become fixed for the rest of the war. Each death eater will maximize his/her power. After they fix their power, the war starts. Hermione and other members of the Order of Phoenix want to fight them individually (i.e. duel), but to do that they need to perform a special spell which splits the line or any segment of the line into two parts. The cost of performing this spell is equal to the sum of the power of the death eaters in that segment. Say, there are 3 death eaters and their power are 2, 1, 2 (Sample Case 2). Now if the splitting spell is performed between 1st and 2nd death eater, the 1st one becomes alone and 2nd and 3rd one are still together. So, in this case, if the first splitting spell is performed between 1st and 2nd, the cost is 2 + 1 + 2 = 5. Then the 2nd spell has to be performed between 2nd and 3rd death eater, which will cost 1 + 2 = 3. So the total cost is 8. Hermione needs your help to minimize the total cost of splitting spells to make each death eater alone. Input First line of the input contains a positive integer, T (T ≤ 300) which denotes the number of test cases. For each case, the first line contains the number of death eaters, n (1 ≤ n ≤ 1000). The second line contains n positive integers denoting the strength of death eaters in the line (Left to Right i.e. i − 1 isontheleftsideofiandi+1isontherightsideofiand(2≤i≤n−1). Allintegersarelessthan 1,000,000. Output For each of the cases output ‘Case < x >: < y >’ in a separate line, where x is case number, y is minimum total cost to break the union of death eaters. Explanation for Sample Case In the first case, 1st death eater can make a sequence like 4 2 (no smaller strength in the left side). 2nd death eater can make a sequence 4 5 2, increasing in the left side 4 5 and decreasing in the right side 5 2. 3rd death eater can make a sequence 2 (no smaller strength in the left side and also no smaller strength in the right side). So powers of them are 2, 3 and 1. To break the union of death eater one can perform splitting spell between 2nd and 3rd death eater which will cost 2 + 3 + 1 = 6 and then perform splitting spell between 1st and 2nd death eater which will cost 2 + 3 = 5. So the total cost is 6 + 5 = 11. But if one perform splitting spell between 1st and 2nd death eater it will cost 2 + 3 + 1
2/2 = 6 and then perform splitting spell between 2nd and 3rd death eater it will cost 3 + 1 = 4. So the total cost is 6 + 4 = 10 and it is minimum cost to break the union of death eaters. Sample Input 2 3 452 3 425 Sample Output Case 1: 10 Case 2: 8