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. \)