Given an array \(A\) of \(N\) integers, the goal is to rearrange the elements in the array \(A\) so that the magic value of the array is maximized.

The magic value is calculated by finding the length of the longest increasing subsequence of the original array \(A\) and the longest increasing subsequence of the reverse of the array \(A\). The magic value is defined as the minimum of these two lengths. The task is to rearrange the elements in \(A\) to obtain the maximum possible magic value.

A sequence consisting of \(N\) elements \(a_1, a_2, \cdots, a_N\). A subsequence \(a_{i_1}, a_{i_2}, \cdots, a_{i_k}\) where \(1 ≤ i1 < i2 < \cdots < ik ≤ N\) is called increasing if \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). An increasing subsequence is called the longest if it has the maximum length among all increasing subsequences.

Input format

The first line contains a single integer \(T\) denoting the number of test cases.
The first line of each test case contains the integer \(N\), the number of elements in the arrays \(A\).
The second line will contain \(N\) space-separated integers, the elements of the array \(A\).

Output format

For each test case, print the maximum possible magic value after rearranging the elements in \(A\).

Constraints

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 0≤A[i]≤10^9\ ∀\ i∈[1,N]\)