You are given an integer array of integers. In one operation, you can do the following:
Choose any two adjacent elements in the array, let's say, a_i and a_{i+1}. Then, delete them, and add |a_i - a_{i+1}| to your score.
Note that the indices are recalculated after the operation.
You are going to perform this operation times, deleting all the elements in the end. What is the largest score you can get?
The first line contains a single integer (1 \le t \le 10^5) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer (1 \leq n \leq 2\cdot 10^5).
The second line of each test case contains integers a_1, a_2, \ldots, a_{2n} (0 \leq a_i \leq 10^9) — elements of the array.
It is guaranteed that the sum of over all test cases does not exceed 2\cdot 10^5.
For each test case, output a single integer — the largest possible score you can get after performing the operation times.
Example
In the first test case, we can choose the first two elements, and delete them, getting score of , and then choose the remaining two elements, delete them, getting score of again.
In the second test case, the only possible operation is to choose both elements and to get score of |42-69| = 27.
In the third test case, we can do the following sequence of operations:
Choose elements . Delete them, and get a score of . The array will become [1, 2, 5, 6].
Choose elements . Delete them, and get a score of . The array will become .
Choose elements . Delete them, and get score of . The total score is 1+3+5 =9.