C. Concert Queue
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tickets for the latest BLACKPINK concert just went on sale, and $$$n$$$ fans are lined up at the box office, served strictly one at a time in queue order. The $$$r$$$-th fan in the queue takes $$$a_r$$$ minutes to be served.

The waiting time of a fan is the total serving time of all fans at or before them in the queue: the waiting time of the $$$r$$$-th fan equals $$$a_1 + a_2 + \ldots + a_r$$$. The cost of the queue is the sum of the waiting times of all $$$n$$$ fans.

Jennie is working the box office, and before it opens she may choose exactly one fan and move them to the very front of the queue (a VIP pass!). All other fans keep their relative order.

Find the minimum possible cost of the queue after this move. Note that choosing the fan already at the front leaves the queue unchanged.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of fans in the queue.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the serving times of the fans, in queue order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum possible cost of the queue after moving exactly one fan to the front.

Example
Input
3
4
3 1 4 2
1
5
3
1 2 3
Output
23
5
10
Note

In the first test case, the queue is $$$[3, 1, 4, 2]$$$ with cost $$$3 + 4 + 8 + 10 = 25$$$. Moving the second fan to the front gives $$$[1, 3, 4, 2]$$$ with waiting times $$$1, 4, 8, 10$$$ and cost $$$23$$$, which is optimal. (Moving the fourth fan to the front, giving $$$[2, 3, 1, 4]$$$, also achieves cost $$$23$$$.)

In the second test case, there is only one fan, so the queue stays $$$[5]$$$ and the cost is $$$5$$$.

In the third test case, the queue $$$[1, 2, 3]$$$ is already optimal: Jennie gives the VIP pass to the fan already at the front, the queue is unchanged, and the cost is $$$1 + 3 + 6 = 10$$$.