Problem Description

MZL is a mysterious mathematician, and he proposed a mysterious function at his young age.
Stilwell is very confused about this function, and he need your help.
First of all, given n positive
integers Ai and Ai≥Ai+1.
Then, generate n positive
integers Bi

Define f(i,j) for i,j∈Z

Find f(n,1).

 

Input

The first line of the input contains a single number T,
the number of test cases.
For each test case, the first line contains a positive integer n,
and the next line contains n positive
integers Ai.
T≤100, 1≤n≤105, ∑n≤106, 1≤Ai≤104.

 

Output

For each test case, output f(n,1) in
a line.

 

Sample Input

 

Sample Output

#include <iostream>

#include <cstdio>

#include<algorithm>

#include<cstring>

#include<functional>

#include<queue>

typedef long long ll;

using namespace std;

int main()

{

    int T;

    int n,a;

    priority_queue<ll, vector<ll>, greater<ll> >q;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        while(!q.empty())

        {

            q.pop();

        }

        for(int i=1; i<=n; i++)

        {

            scanf("%d",&a);

            q.push(a);

        }

        ll sum = 0;

        while(!q.empty())

        {

            ll x = q.top();

            q.pop();

            if(q.empty())

            {

                continue;

            }

            ll y = q.top();

            q.pop();

            ll tmp= x + y;

            sum+=tmp;

            q.push(tmp);

        }

        printf("%I64d\n",sum);

    }

    return 0;

}