题目描述

给定一个整数数组 $a_1, a_2, \ldots, a_n$。我们称数组 $x_1, x_2, \ldots, x_m$ 是美丽的，如果存在一个数组 $y_1, y_2, \ldots, y_m$ 满足以下条件：

• $y$ 数组中的元素互不相同（即对于所有 $1 \le i < j \le m$ 有 $y_i \neq y_j$）
• 对于所有 $1 \le i \le m$，$x_i$ 和 $y_i$ 的乘积都相同（即对于所有 $1 \le i < j \le m$ 有 $x_i \cdot y_i = x_j \cdot y_j$）

你的任务是找出数组 $a$ 的最长子序列 $^{\text{∗}}$ 的长度，使得这个子序列是美丽的。

$^{\text{∗}}$ 序列 $b$ 是序列 $a$ 的子序列，当且仅当 $b$ 可以通过从 $a$ 中删除任意数量（可以是零个或全部）的元素得到。

输入格式

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 500$）。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）——数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。

注意题目没有对所有测试用例的 $n$ 之和做出限制。

输出格式

对于每个测试用例，输出数组 $a$ 的最长美丽子序列的长度。

说明/提示

在第一个测试用例中，整个数组 $a = [1, 2, 3]$ 已经是美丽的。一个可能的 $y$ 数组是 $[6, 3, 2]$，这满足条件因为：

• $y$ 数组元素互不相同
• $1 \cdot 6 = 2 \cdot 3 = 3 \cdot 2 = 6$

在第二个测试用例中，子序列 $[3, 1, 4, 5]$ 是美丽的。一个可能的 $y$ 数组是 $[20, 60, 15, 12]$。可以证明整个数组 $a = [3, 1, 4, 1, 5]$ 不是美丽的，因此最长的美丽子序列长度是 $4$。

翻译由 DeepSeek V3 完成

样例

3
3
1 2 3
5
3 1 4 1 5
1
1

3
4
1