Max Minus Min#12945

Max Minus Min

You are given array of integers. You can perform the following operation at most once:

Find the smallest possible value of \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n) you can get after performing this operation at most once.

Input

The first line contains a single integer (1 \le t \le 10^5)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer (1 \leq n \leq 2\cdot 10^5)  — the length of the array.

The second line of each test case contains integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq 10^9)  — elements of the array.

It is guaranteed that the sum of over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, in the first line output a single integer  — the smallest possible value of \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n) you can get after performing this operation at most once.

Examples

Example

Loading
Loading

Note

In the first test case, you don't need to make any operations, since max - min = 0 already.

In the second test case, you can choose x = -1, and segment a[2:3]. The array will become [1, 1, 1, 1], with max - min = 0.

In the third test case, max - min initially is . Unfortunately, it's not possible to decrease this value with a single operation.

In the fourth test case, max - min initially is , but we can choose x = 3 and segment a[1:3]. The array will become [4, 5, 6, 4, 5, 6], with max - min = 2.