Life Is All About Balance

Given an array $A$ of $N$ integers, the array will be balanced if you can select at least one index $i(1 \leq i < N)$ and divide the array into two non empty subarrays, $B$ $=$ $\{A_1, A_2, .. , A_i\}$ and $C$ $=$ $\{A_{i+1}, A_{i+2}, .. , A_N\}$ such that $F(B) = F(C)$.

$F(V)$ for the subarray $V$ is defined as the difference between the maximum and the minimum element of $V$. For example if $V$ ${= \{3, 6, 2, 0\}}$, then $F(V)$ ${= max \{3, 6, 2, 0\} - min \{3, 6, 2, 0\}}$ ${= 6 - 0}$ ${= 6}$.

Before dividing the array, you can do one type of operation to the array any number of times(possibly zero). Select any index $j$ ($1 \leq j \leq N$) and any integer $x$ ($0 \leq x \leq 2 \times 10^9$) and set $A_j$ = $x$.

You need to output the minimum number of operations required to make the array balanced. It is guaranteed that any array can be made balanced under the given constraints by applying a finite number of operations.

Input

The input contains multiple test cases. The first line of input contains one integer $T$ ($T$$1 \leq T \leq 2\times10^4$) the number of test cases.

The first line of each test case contains one integer $N$ ($2 \leq N \leq 5\times10^5$) the size of the array.

The second line of each test case contains $N$ integers $A_1$, $A_2$, …, $A_N$ ($0 \leq A_i \leq 10^9$).

It is guaranteed that the sum of $N$ over all test cases does not exceed $5\times10^5$.

Output

For each test case, print one integer — the minimum number of operations required to make the array balanced.

Sample

Input	Output
2 2 12 12 6 1 3 6 10 6 4	0 1
For the first test case, the array is already Balanced. For the second test case, we can do one operation to make the array Balanced. We can select $j$ $= 4$ and $x$ $= 9$ and set $A_4$ $= 9$. Then the array will be ${\{1, 3, 6, 9, 6, 4\}}$. We can select index $i$ $= 3$ to divide the array into two subarrays, $B = \{1, 3, 6\}$ and $C = \{9, 6, 4\}$. $F(B)$ ${= max\{1, 3, 6\}}$ $-$ ${min\{1, 3, 6\}}$ $= 6 - 1$ $= 5$. $F(C)$ $= max\{9, 6, 4\}$ $-$ $min\{9, 6, 4\}$ $= 9 - 4$ $= 5$. So the array is Balanced.