E. Interesting Alternating Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a permutation $$$p$$$ of size $$$n$$$ and a piece of pseudocode:

    sum:=0
    for i:=1 to n 
        sort(1,i)        #sort p[1],p[2],...p[i] in ascending order
        for j:=1 to n
            if(j is odd) sum:=sum+p[j]
            else         sum:=sum-p[j]

Output the final value of the variable $$$sum$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of one line of input.

The first line of each test case contains an integer $$$n(1 \leq n \leq 4 \cdot 10^5)$$$.

The second line contains $$$n$$$ integers $$$p_1,p_2,...,p_n(1 \le p_i \le n,p$$$ is a permutation $$$)$$$.

The sum of $$$n$$$ over all will not exceed $$$4 \cdot 10^5$$$.

Output

For each test case,output on a new line — the final value of the variable $$$sum$$$.

Example
Input
4
2
2 1
3
3 1 2
4
1 2 3 4
8
7 1 6 4 8 2 5 3
Output
0
6
-8
30
Note

Test Case $$$1$$$:

When $$$i=1,p=[2,1]$$$.The current value of $$$sum=0+2-1=1$$$;

When $$$i=2,p=[1,2]$$$.The current value of $$$sum=1+1-2=0$$$.

Test Case $$$2$$$:

When $$$i=1,p=[3,1,2]$$$.The current value of $$$sum=0+3-1+2=4$$$;

When $$$i=2,p=[1,3,2]$$$.The current value of $$$sum=4+1-3+2=4$$$;

When $$$i=3,p=[1,2,3]$$$.The current value of $$$sum=4+1-2+3=6$$$.