You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :

1. Each weight should be a positive integer.
2. W[1] = 1
3. W[i] should be in the range [2, W[i-1] + 1] for i > 1

Weighted sum is defined as S = A[1] × W[1] + A[2] × W[2] + ... + A[N] × W[N]

Input

There are multiple test cases.
First line contains the number of test cases
Each test case consists of a single line containing N.
This is followed by N lines, each containing A[i]

Output

For each test case, output one line - the maximum weighted sum.

Example

Input:
1 
4 
1 
2 
3 
-4

Output:
6

Explanation

Constraints

N ≤ 10⁶
| A[i] | ≤ 10⁶
Total number of test cases is around 10.