The weight of an array is defined as the difference between the maximum and minimum element of the array. For example, the weight of the array [3, 7, 1, 2] is (7 - 1) = 6, the weight of the array [2] is (2 - 2) = 0, the weight of an empty array is 0.
You are given an array A of length N. You have to divide the elements of A into two subsequences S1, and S2 (one of S1, S2 can be empty) such that:

Each element of A belongs to one of S1 and S2.
The sum of weights of the two subsequences is maximum.

Find the maximum possible sum of weights of the two subsequences.

Input format

The first line contains T denoting the number of test cases. The description of T test cases is as follows:
For each test case:
- The first line contains N denoting the size of array A.
- The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting the elements of A.

Output format
For each test case, print the maximum possible sum of weights of the two subsequences.

Constraints

\(1 \leq T \leq 10^4 \\ 2 \leq N \leq 10^5\\ \\1\leq A_i \le 10^9 \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;2\cdot 10^5. \)