← 返回题目列表

Codeforces · 1977/C

C. 尼基塔和 LCM

中文机器翻译题面 查看原题

Nikita 是一名热衷于数论和算法的学生。他面临一个与数字数组相关的有趣问题。

假设 Nikita 有一个长度为 $$$n$$$ 的整数数组 $$$a$$$。如果 $$$a$$$ 中不包含该数组的子序列 $$$^\dagger$$$,则该子序列的最小公倍数 (LCM) 不包含在该子序列中。空子序列的 LCM 等于 $$$0$$$。

Nikita 想知道:$$$a$$$ 的最长特殊子序列的长度是多少?帮他回答一下这个问题吧!

$$$^\dagger$$$ 序列 $$$b$$$ 是 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$a$$$ 获得,而不改变其余元素的顺序。例如,$$$[5,2,3]$$$ 是 $$$[1,5,7,8,2,4,3]$$$ 的子序列。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) - 测试用例的数量。测试用例的描述如下。

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

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出一个整数 - $$$a$$$ 的最长特殊子序列的长度。

示例

输入 #1

6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1

输出 #1

0
4
4
5
8
0

注意

在第一个测试用例中,任何非空子序列的LCM都包含在$$$a$$$中,因此答案是$$$0$$$。

在第二个测试用例中,我们可以取子序列$$$[3, 2, 10, 1]$$$,它的LCM等于$$$30$$$,它不包含在$$$a$$$中。

在第三个测试用例中,我们可以取子序列$$$[2, 3, 6, 100\,003]$$$,它的LCM等于$$$600\,018$$$,它不包含在$$$a$$$中。