Ehab 有一个长度为 $$$n$$$ 的数组 $$$a$$$。他有足够的空闲时间来创建一个新数组,其中包含旧数组的 $$$n$$$ 副本,并连续写入。新数组的最长递增子序列的长度是多少?
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是数组 $$$b$$$ 的子序列。数组的最长递增子序列是其元素严格按递增顺序排序的最长子序列。
输入
第一行包含一个整数 $$$t$$$ — 您需要解决的测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 中的元素数量。
第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果将 $$$a$$$ 与其自身连接 $$$n$$$ 次,则输出 $$$a$$$ 的最长递增子序列的长度。
示例
输入 #1
2 3 3 2 1 6 3 1 4 1 5 9
输出 #1
3 5
注意
在第一个示例中,新数组为 $$$[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$$$。最长的递增子序列以粗体标记。
在第二个样本中,最长的递增子序列将为 $$$[1,3,4,5,9]$$$。