Migrated from Lutece 1667 Sorting

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

We have an array and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array. You are to write a program that will find the minimum cost to sort such an array.

Input

First line of the input contains $T$ the number of test cases. For each test case the first line contains an integer $N$ $(1 ≤ N ≤ 100)$. The second line contains $N$ positive integers separated by spaces. These integers denote the array. Each of these integers is between $1$ and $1000$ inclusive.

Output

For each case, the output contains an integer denoting the minimum cost to sort the array.

Samples

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

6
7 
18

Resources

Malaysia > Al-Khawarizmi National Programming Contest 2011 Problem H