#526. 「LibreOJ β Round #4」子集

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: qmqmqm

题目描述

一个可重集合中包含 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

输出格式

输出一个整数代表符合条件的元素最多的子集的元素个数。

样例

样例输入1

3
4
6
9

样例输出1

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}