You start with an integer array $$$a$$$, which initially consists of $$$n$$$ zeros. You have to perform the following action exactly $$$n$$$ times:

choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and assign $$$a_{i} = a_{i} + 1$$$ for each $$$i$$$ such that $$$l \le i \le r$$$.

You are given an array $$$b$$$, consisting of $$$n$$$ integers. Your task is to choose such values $$$l$$$ and $$$r$$$ for each action that:

after all $$$n$$$ actions are performed, it's possible to reorder the elements in such a way that $$$a$$$ becomes equal to $$$b$$$;
the maximum value of $$$r - l + 1$$$ over all actions is as large as possible.

What's the maximum possible value of $$$r - l + 1$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the length of the array $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$b_{i}$$$ ($$$0 \le b_{i} \le n$$$) — the elements of the array $$$b$$$.

Additional constraints on the input:

there exists at least one way to choose $$$l$$$ and $$$r$$$ for each action and reorder the elements at the end so that $$$a$$$ becomes equal to $$$b$$$;
the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the answer to the problem.

Note

Consider the first test case. If the $$$n$$$ actions were as follows:

$$$l = 3$$$ and $$$r = 3$$$
$$$l = 1$$$ and $$$r = 3$$$
$$$l = 3$$$ and $$$r = 3$$$
$$$l = 3$$$ and $$$r = 3$$$
$$$l = 3$$$ and $$$r = 3$$$

The array $$$a = [1, 1, 5, 0, 0]$$$, so you can reorder the elements to make it equal to $$$[0, 5, 1, 0, 1]$$$. As can be seen in this case, the maximum value of $$$r - l + 1$$$ is $$$3$$$. It can be shown that this is the optimal answer.

In the second test case:

$$$l = 1$$$ and $$$r = 3$$$
$$$l = 2$$$ and $$$r = 3$$$
$$$l = 3$$$ and $$$r = 3$$$

The answer is $$$3$$$.

Addition on a Segment

Examples