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]$