Problem Description

For a sequence $X:\{x_1,x_2,...,x_L\}$ of length $L \ge 2$, if for any $1 \le i < j \le L$, $x_i + x_j$ is not a prime number, then JYY considers the sequence $X$ to be an “anti-prime sequence”.

JYY has a sequence $A:\{a_1,a_2,...,a_N\}$ of length $N$. He wants to choose a subsequence with as many elements as possible such that this subsequence is an anti-prime sequence.

Input Format

The first line contains a positive integer $N$.

The next line contains $N$ positive integers, describing $a_1,a_2,...,a_N$ in order.

Output Format

Output one integer in a single line, representing the length of the longest anti-prime subsequence. The input guarantees that an anti-prime subsequence exists.

6
1 2 2 3 4 10

4

Hint

For $10\%$ of the testdata, $N \le 10$.

For $40\%$ of the testdata, $N \le 150$.

For $80\%$ of the testdata, $N \le 1000$.

For $100\%$ of the testdata, $2 \le N \le 3000$, $1 \le a_i \le 10^5$.

Translated by ChatGPT 5