C. Trinitytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array $$$a$$$ of $$$n$$$ elements $$$a_1, a_2, \ldots, a_n$$$.You can perform the following operation any number (possibly $$$0$$$) of times: Choose two integers $$$i$$$ and $$$j$$$, where $$$1 \le i, j \le n$$$, and assign $$$a_i := a_j$$$. Find the minimum number of operations required to make the array $$$a$$$ satisfy the condition: For every pairwise distinct triplet of indices $$$(x, y, z)$$$ ($$$1 \le x, y, z \le n$$$, $$$x \ne y$$$, $$$y \ne z$$$, $$$x \ne z$$$), there exists a non-degenerate triangle with side lengths $$$a_x$$$, $$$a_y$$$ and $$$a_z$$$, i.e. $$$a_x + a_y > a_z$$$, $$$a_y + a_z > a_x$$$ and $$$a_z + a_x > a_y$$$. InputEach test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output a single integer — the minimum number of operations required.ExampleInput471 2 3 4 5 6 731 3 234 5 3159 3 8 1 6 5 3 8 2 1 4 2 9 4 7Output3 1 0 8 NoteIn the first test case, one of the possible series of operations would be: Assign $$$a_1 := a_4 = 4$$$. The array will become $$$[4, 2, 3, 4, 5, 6, 7]$$$. Assign $$$a_2 := a_5 = 5$$$. The array will become $$$[4, 5, 3, 4, 5, 6, 7]$$$. Assign $$$a_7 := a_1 = 4$$$. The array will become $$$[4, 5, 3, 4, 5, 6, 4]$$$. It can be proven that any triplet of elements with pairwise distinct indices in the final array forms a non-degenerate triangle, and there is no possible answer using less than $$$3$$$ operations.In the second test case, we can assign $$$a_1 := a_2 = 3$$$ to make the array $$$a = [3, 3, 2]$$$.In the third test case, since $$$3$$$, $$$4$$$ and $$$5$$$ are valid side lengths of a triangle, we don't need to perform any operation to the array.