Xsquare loves to play with arrays a lot. Today, he has an array A consisting of N distinct integers. He wants to perform following operation over his array A.

• Select a pair of consecutive integers say (A_i,A_i+1) for some 1 ≤ i < N. Replace the selected pair of integers with the max(A_i,A_i+1).
• Replace N with the new size of the array A.
• Above operation incurs a cost of rupees max(A_i,A_i+1) to Xsquare.

As we can see after N-1 such operations, there is only 1 element left. Xsquare wants to know the most optimal transformation strategy to reduce the given array A to only 1 element.

A transformation strategy is considered to be most optimal if it incurs minimum cost over all possible transformation strategies.

Input

First line of input contains a single integer T denoting the number of test cases. First line of each test case starts with an integer N denoting the size of the array A. Next line of input contains N space separated integers, where i^th element denotes the value A_i.

Output

For each test case, print the minimum cost required for the transformation.

Constraints

1 ≤ T ≤ 10⁵

2 ≤ N ≤ 10⁵

1 ≤ A_i ≤ 10⁹

sum of N over all test case does not exceed 5*10⁵

Subtasks

• Subtask 1: 1 ≤ T ≤ 10 , 2 ≤ N ≤ 17 ( 20 % )
• Subtask 2: sum of N does not exceed 5*10³ ( 30 % )
• Subtask 3: sum of N does not exceed 5*10⁵ ( 50 % )

Warning :

Prefer to use printf / scanf instead of cin / cout .