题目内容

有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，序列中的每个元素都是 $1$ 到 $n$ 之间的整数。现在将这个序列无限次地拼接在自己末尾，形成一个无限长的序列 $b$，具体来说：对于任意正整数 $i$，若 $i > n$，则 $b_i = b_{i-n}$。

小力想要从无限序列 $b$ 中选取一个子序列，要求子序列中的元素 互不相同。请问，他最多能选出多少个元素？

子序列的定义：从原序列中删除任意个元素后，其余元素按原有顺序组成的新序列。

你需要回答 $T$ 组独立的测试数据。

数据范围与约束：

• 测试数据组数 $T$ 不超过 $10^4$。
• 序列长度 $n$ 不超过 $2 imes 10^5$，且所有测试数据的 $n$ 之和不超过 $2 imes 10^5$。
• 序列中的元素 $a_i$ 均为整数，满足 $1 \le a_i \le n$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 对于每组数据： 第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示给定的序列。

输出描述

对于每组测试数据，输出一行一个整数，表示从无限序列 $b$ 中能够选出的最长互不相同子序列的长度。

样例1

输入

1
1
1

输出

1

说明

只有一组测试数据，序列长度为 1，序列为 $a = [1]$。无限拼接后，序列 $b$ 中的所有元素都是 1。无论怎样选取子序列，最多只能得到 1 个互不相同的元素，因此答案是 1。

样例2

输入

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

输出

1
5

说明

共两组数据。 第一组：序列 $a = [2, 2, 2, 2]$，无限拼接 $b$ 中仅出现数字 2，不同元素个数为 1。 第二组：序列 $a = [3, 1, 4, 1, 5, 9]$，其中出现的不同数字有 3、1、4、5、9，共 5 个。由于序列是无限重复的，我们可以依次将这些互不相同的元素选出来，因此答案为 5。

样例3

输入

1
3
1 2 3

输出

3

说明

序列 $a = [1, 2, 3]$，三个元素均互不相同。在无限拼接得到的序列 $b$ 中，每个元素都反复出现，我们可以直接选择子序列 $[1, 2, 3]$，长度为 3，且无法选出更多互不相同的元素，因此答案为 3。