H. 最长好子序列
时间限制：7 秒
内存限制：1024 兆字节

如果一个长度为 $m$ 的数组 $b$ 满足以下条件，则称它是好的：

1. 对每个 $1 \le i \le m$，有 $1 \le b_i \le i$。
2. 存在一个长度为 $m$ 的排列 $p$，使得对每个 $1 \le i \le m$，$b_i$ 是满足 $\min(p_{b_i}, p_{b_i+1}, \dots, p_i) = p_i$ 的最小整数。

例如，数组 $[1,1,3,3,5]$ 是好的（排列 $p = [2,1,5,3,4]$ 满足第二个条件），但数组 $[1,1,2]$ 不是好的。

注意，空数组被认为是好的。

给定一个长度为 $n$ 的数组 $a$。找出 $a$ 的最长好子序列$^\dagger$ 的长度。

$^\dagger$ 序列 $c$ 是序列 $d$ 的子序列，如果 $c$ 可以通过删除 $d$ 中的若干（可能为零或全部）元素（不改变剩余元素的相对顺序）得到。

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 15000$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）—— 数组 $a$。

保证所有测试用例的 $n^2$ 之和不超过 $15000^2$。

输出
对于每个测试用例，输出一行，包含最长好子序列的长度。

样例
输入

5
5
1 1 3 3 5
3
1 1 2
4
2 2 2 2
7
1 2 4 2 4 6 2
1
1

输出

5
2
0
5
1

说明

• 第一个测试用例中，整个序列本身就是好的。
• 第二个测试用例中，最长好子序列是 $[1,2]$。