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