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$$$中。