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