E. A Distinct Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers. In one operation, you may delete any single element of the array.

Call a non-empty array good if its largest element minus its smallest element is strictly less than the number of distinct values it contains. Formally, a non-empty array $$$b$$$ with $$$k$$$ distinct values is good if $$$\max(b) - \min(b) \lt k$$$, where $$$\max(b)$$$ and $$$\min(b)$$$ are the largest and smallest elements of $$$b$$$, respectively.

For example, $$$[7, 7]$$$ is good, since $$$\max(b) - \min(b) = 0$$$ is less than its $$$1$$$ distinct value. But the array $$$[2, 9]$$$ is not good, since $$$\max(b) - \min(b) = 7$$$, but it has only $$$2$$$ distinct values, and $$$7 \not \lt 2$$$.

Determine the minimum number of operations needed to make the array $$$a$$$ good. It is always possible to do so, since any array consisting of a single element is good.

Input

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

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

Output

For each test case, output a single integer — the minimum number of operations needed to make the array good.

Example
Input
2
4
8 6 2 4
2
7 9
Output
3
1
Note

In the first test case, deleting $$$8$$$, $$$6$$$, and $$$4$$$ leaves $$$[2]$$$, which is good ($$$\max - \min = 0$$$, less than its $$$1$$$ distinct value). No sequence of fewer than $$$3$$$ deletions works.