题目描述

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$ 次后所得新数组的最长严格递增子序列的长度。

说明/提示

在第一个样例中，新数组为 $[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$。最长递增子序列已用粗体标出。

在第二个样例中，最长递增子序列为 $[1,3,4,5,9]$。

由 ChatGPT 4.1 翻译

样例

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

3
5