You are given an array of N integers. The power of this array is the sum of power of every element of the array. The power of any element is the total number of element (including it) in the array that are not greater than this element. For example:

If the array contains 3 elements and they are 1, 2, 3 then the power of this array is 1 + 2 + 3 = 6.

Input

First line contains test cases t (1 <= t <= 100). Each of the test case contains two lines. First line contains the value of N (1 <= N <= 50000) and second line contains N space separated positive integers less than or equal to 50000.

Output

For each test case print the power of the array.

Example

Input:
2
2
1 2
3
1 2 3

Output:
3
6