Extra Point

Time Limit: 3 Seconds    Memory Limit: 262144 KB

Dr. MT is a faculty member of Sh. University and teaches the undergraduate students “Fundaments of Programming”. He likes to encourage his students to compete in weekly contests held in the university. Hence, he decided to assign an extra point to each student who competes in these contests according to the following rules:

  •  The student should compete in all contests.
  •  Extra point is assigned to the student only for valid contests, in which the number of solved problems is not less than the ones of the previous contests.
  •  Extra point of each valid contest is as much as the number of solved problems.
  •  Overall extra point is the sum of extra points achieved in the contests.

At the first day, one of the students knows how many problems he can solve in each contest. However, the maximum extra point is not certainly achieved by doing his best in all contests. He wants to calculate the maximum extra point.

Input

The input is started by an integer 0<t≤10 followed by t test cases. Each test case is represented by two lines. In the former, a positive integer N is given as the number of contests (i.e. 1<N≤8,000). In the latter, N space-separated integers have given such that the ith number indicates the number of problems the student can solve in the ith contest. Each contest has exactly 100,000 problems and there is enough time to solve all of them for an intelligent student.

Output

For each test case, output in a separate line, the maximum extra point.

Sample Input

4
2
3 5
2
5 3
4
5 10 6 20
10
10 9 8 7 6 5 4 3 2 1

Sample Output

8
6
37
30
Submit

Source: 12th Iran Nationwide Internet Contest IV