Symmetry Shuffle

You are given an array of integers $a_1, a_2, \dots, a_n$. Your task is to make the array symmetrical with the minimum number of operations.

Definition of a Symmetric Array: An array $b_1, b_2, \dots, b_n$ is considered symmetrical if $b_i = b_{n-i+1}$ for all $1 \leq i \leq n$.

Operations Allowed: Before performing any operations, you may shuffle the elements of the array in any order you like. Then, you can perform the following operation any number of times:

• Choose an index $1 \leq i \leq n$ and increment the value of $a_i$ by 1, i.e., set $a_i = a_i + 1$.

Objective: Determine the minimum number of operations required to make the array symmetrical.

It's guaranteed that you can always make an array symmetrical.

Input Format:

• The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases.
• The first line of each test case contains a single integer $n$ $(1 \leq n \leq 10^5)$ — the number of elements in the array. The sum of $n$ over all sets of input data does not exceed $10^5$.
• The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^9)$ — the elements of the array.

Output Format: For each test case, output the minimum number of operations required to make the array symmetrical.

Examples

Input

3
4
1 3 3 1
5
2 3 3 2 1
3
1 2 3

Output

0
0
1

1. An array of 4 elements: 1 3 3 1.

2. An array of 5 elements: 2 2 1 3 3.

3. move 1 to the middle to get 2 1 3 and add 1 to 2 to get 3 1 3

Input

4
4 
7 1 5 3
7 
1 8 2 16 8 16 31
5 
11 2 15 7 10
13 
2 1 1 3 3 11 12 22 45 777 777 1500 74

Output

4
1
6
48