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