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

Longest Good Subsequence

Examples