题目描述

Nezzar 有 $n$ 个球，编号为 $1, 2, \ldots, n$。每个球上分别写有数字 $a_1, a_2, \ldots, a_n$。这些数字构成一个非递减序列，即对于所有 $1 \leq i < n$，都有 $a_i \leq a_{i+1}$。

Nezzar 想用最少的颜色给这些球染色，使得满足以下条件：

• 对于任意一种颜色，若只保留这种颜色的球并丢弃其他球，则这些球上的数字将构成一个严格递增序列。

注意，长度不超过 $1$ 的序列也被认为是严格递增序列。

请你帮助 Nezzar 求出他最少需要多少种颜色。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。保证 $a_1 \leq a_2 \leq \ldots \leq a_n$。

输出格式

对于每个测试用例，输出 Nezzar 至少需要多少种颜色。

说明/提示

我们可以将每种颜色与一些数字对应起来。例如：

在第一个测试用例中，一种最优的染色方案为 $[1,2,3,3,2,1]$。

在第二个测试用例中，一种最优的染色方案为 $[1,2,1,2,1]$。

由 ChatGPT 4.1 翻译

样例

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

3
2
4
1
1