HZNUOJ

古茗

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:213     AC:41     Score:100.00

Description

暑假到了,zkl学姐又开始喝奶茶了,而且还时常抱怨他的队友天天喝奶茶。

在西南门的那家古茗只有$n$杯奶茶了,第$i (1 \leq i \leq n)$杯奶茶的价格为$ai$元。

为了限制这股喝奶茶的恶劣风气,zkl学姐想在购买奶茶的时候增加限制:

· 在购买的奶茶中,没有两杯奶茶的价格之和为素数

但是zkl学姐有无限的钱,请问zkl学姐最多能买多少杯奶茶。


Input

输入第一行包含一个正整数 $n$ $(2 \leqslant n \leqslant 3000 )$。
接下来一行包含 n 个正整数,依次描述$a1,a2,......,an$ $(1 \leqslant ai \leqslant 10^5)$。

Output

输出一行一个数字,代表zkl学姐能够购买奶茶的最大数量。

Samples

input
6 1 2 2 3 4 10
output
4

Hint

zkl学姐可以购买两杯价格为2元的奶茶,一杯价值为4元的奶茶,一杯价值为10元的奶茶,一共四杯奶茶

不用担心zkl学姐喝不完

Author

ZHANG, Chuan