You are a salesman and your goal is to visit all the houses along a certain street.

You walk at a constant rate and can start and end at any location. You may visit the houses in any order you wish. Given the locations of the houses along the street, what is the minimum amount of time needed for you to visit all the houses?

Formally, we represent the street as a number line and the positions of the houses as numbers along this line.

There are n houses numbered 1,2,...,n, and they are located at x(1),x(2),x(3)....,x(n) respectively. Assume that it takes 0(negligible) time to visit a house, and walking from i house to j house takes | x(i) - x(j) | minutes. Print the minimumTime and write a code which takes an integer array , denoting the locations of the houses as input. Return an integer denoting the minimum amount of time, in minutes, needed to visit all the houses.

Input Format

The first line contains a single integer t denoting the number of streets. The description of t streets follow.

Each street is described by two lines. The first line contains a single integer n denoting the number of houses in that street.The second line contains integers n denoting the locations x(1),x(2),x(3)....,x(n) of the houses along the street.

Constraints

• 1<=t<=500
• 1<=n<=50(So there may be only one house)
• 1<=x(i)<=1000
• The houses' locations are distinct

Subtasks

• For 20% of the maximum score, n <=3
• For 50% of the maximum score,n <=6

Output Format

For each street, print a single line containing a single integer denoting the minimum amount of time, in minutes, needed to visit all the houses.