题目描述

小 z 最近学习了最长上升子序列，于是 w 老师决定出道题来考考他。

什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。

问题如下：

给你一个长为 $n$ 的序列，将它复制 $n$ 遍，形成一个长度为 $n^2$ 的序列。请在这个复制后的序列里找一个最长上升子序列，给出它的长度。

输入格式

第一行输入一个 $T$ 为数据组数。

每组第一行输入 一个 $n$ 为序列长度。

每组第二行输入一个长度为 $n$ 的序列 $a_i$。

输出格式

$T$ 行，每行一个整数，表示最长上升子序列的长度

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

3
5

提示

样例解释

Case#1:

$\{3,2,1,3,2,1,3,2,1\}$，我们选择子序列为 $\{1,2,3\}$

Case#2:

我们选择的子序列为 $\{1,3,4,5,9\}$

数据范围

对于 $100\%$ 的数据满足 $0≤a_i≤10^9,0≤\sum{n}≤10^5$，即所有输入 $n$ 之和小于 $10^5$。