Fried-chicken hates origami problems! He always fails at solving origami problems that others can solve easily (for example, CF1966E and HDU6822). However, today Fried-chicken is the problem setter! It’s his turn to give contestants a very difficult origami problem!

Given an array of length , you can perform the following operations any number of times (possibly zero):

Choose an index , and then perform one of the following two operations:

1. For all such that , let .

2. For all such that , let .

For example, if the original array is and you choose and perform operation 1, the array will become .

Now, you want to minimize the range of the array through these operations. Recall that the range of an array is the difference between the maximum and minimum elements of the array.

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases  (). The description of the test cases follows.

The first line of each test case contains an integer  (), representing the length of the array.

The second line contains  integers  (), describing the elements of the array  in the initial state.

It is guaranteed that the sum of  over all test cases does not exceed .

输出描述:

For each test case, output one integer on a single line, representing the minimum range of the array after any number of operations.

3
4
2 4 5 3
3
1 2 100
1
10000

1
1
0