3977: 「LibreOJ β Round #4」子集
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
一个可重集合中包含 $n$ 个元素 $a_1,a_2,\cdots ,a_n$，你需要选择一个子集，使得这个子集中任意两个元素 $a_i,a_j$ 均满足条件 $\gcd(a_i,a_j)\gcd(a_i+1,a_j+1)\neq 1$，且这个子集的元素个数是所有满足上述条件的子集中最多的。输出这个子集的元素个数。
输入
输入的第一行包含一个正整数 $n$。
随后 $n$ 行，每行一个正整数 $a_i$。
输出
输出一个整数代表符合条件的元素最多的子集的元素个数。
样例输入 复制
3
4
6
9样例输出 复制
3提示
输入样例2
41 71 3 5 50 75 2 19 47 88 95 92 110 111 117 58 124 130 57 129 168 161 29 39 206 79 10 142 107 209 210 222 221 223 242 104 264 265 202 279 314 315
输出样例2
22
数据范围：$1 \leq n \leq 500$ $1 \leq a_i \leq 10^{18}$