← 返回题目列表

Codeforces · 1478/A

A. 内扎尔和彩球

中文机器翻译题面 查看原题

Nezzar 有 $$$n$$$ 个球,编号为整数 $$$1、2、\ldots、n$$$。上面分别写有数字$$$a_1、a_2、\ldots、a_n$$$。这些球上的数字形成非递减序列,这意味着 $$$a_i \leq a_{i+1}$$$ 对于所有 $$$1 \leq i < n$$$。

Nezzar 希望使用最少数量的颜色为球着色,以便满足以下条件。

- 对于任何颜色,如果他保留该所选颜色的球并丢弃所有其他球,则球上的数字将形成严格递增的序列。

请注意,长度至多 $$$1$$$ 的序列被视为严格递增序列。

请帮助 Nezzar 确定最少颜色数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。

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

输出

对于每个测试用例,输出 Nezzar 可以使用的最小颜色数。

示例

输入 #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

输出 #1

3
2
4
1
1

注意

让我们将每种颜色与一些数字相匹配。然后:

在第一个测试用例中,最佳颜色分配是 $$$[1,2,3,3,2,1]$$$。

在第二个测试用例中,最佳颜色分配是 $$$[1,2,1,2,1]$$$。