#2081. 「JSOI2016」反质数序列

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

题目描述

对于一个长度为 L\ge 2 的序列 X:\{x_1,x_2,\cdots ,x_L\} ,如果满足对于任意 1\le i\lt j\le L ,均有 x_i+x_j 不为质数,则 JYY 认为序列 X 是一个「反质数序列」。

JYY 有一个长度为 N 的序列 A:\{a_1,a_2,\cdots ,a_N\} ,他希望从中选出一个包含元素最多的子序列,使得这个子序列是一个反质数序列。

输入格式

输入第一行包含一个正整数 N
接下来一行包含 N 个正整数,依次描述 a_1,a_2,\cdots ,a_N

输出格式

输出一行一个整数,表示最长反质数子序列的长度。输入保证存在反质数子序列。

样例

样例输入

6
1 2 2 3 4 10

样例输出

4

数据范围与提示

对于 10\% 的数据,满足 N\le 10
对于 40\% 的数据,满足 N\le 150
对于 80\% 的数据,满足 N\le 1000
对于 100\% 的数据,满足 2\le N\le 3000,1\le a_i\le 10^5