Call an array $b$ of size $m$ good if the following conditions hold:

• $1 \leq b_i \leq i$ for each $1 \leq i \leq m$.
• There exists a permutation$^{\text{∗}}$ $p$ of size $m$ such that for each $1 \leq i \leq m$, $b_i$ is the smallest integer where $\min(p_{b_i}, p_{b_i+1}, \ldots, p_i)=p_i$.

For example, the array $[1,1,3,3,5]$ is good (where the permutation $p=[2,1,5,3,4]$ satisfies the second requirement), but the array $[1,1,2]$ isn't.

Note the empty array is considered to be good.

You are given an array $a$ of size $n$. Find the length of the longest good subsequence$^{\text{†}}$ of $a$.

$^{\text{∗}}$A permutation of length $m$ is an array consisting of $m$ distinct integers from $1$ to $m$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($m=3$ but there is $4$ in the array). $^{\text{†}}$A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

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 an integer $n$ ($1 \leq n \leq 15\,000$) – the length of $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq n$) — denoting the array $a$.

It is guaranteed that the sum of $n^2$ does not exceed $15\,000^2$ over all test cases.

Output

For each test case, output the length of the longest good subsequence of $a$ on a new line.

Note

In the first test case, the entire sequence is good.

In the second test case, the longest good subsequence is $[1,2]$.