408178: GYM103037 I Creati

Yomo "Creati" Maoyorozu, the Everything Hero, is known for her "quirk" to create objects at will by using the amino acids stored up in her body in tandem with her vast knowledge of chemical compounds. As part of her training, Yomo would like to try to create a never-before-seen object by chaining some subset of $$$N$$$ available amino acids into a protein (for the sake of simplicity, assume the order of chaining acids does not matter in this problem).

Each amino acid has a unique ID that is a positive integer, but Yomo realizes that there is a restriction on certain subsets of amino acids being present in a chain. Her chemistry textbook states that having two acids with IDs that sum to a prime number makes a protein extremely prone to denaturation; thus Yomo would like to refrain from using certain amino acids to make her new object so that no two acids present in synthesis will have IDs that sum to a prime number.

Yomo wants your help to find the largest possible number of amino acids that can still be chained together without the resulting protein being susceptible to denaturation.

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 2000$$$) representing the number of amino acids. The second line of input contains $$$N$$$ space-separated integers $$$r_i$$$ ($$$1 \leq r_i \leq 10^5$$$) indicating the IDs of the amino acids available. All IDs are distinct.

Output a single integer representing the largest number of amino acids that can be chained together such that none of the pairwise sums of their IDs are prime.

4
2 3 5 7

3

6
10 11 12 13 14 15

3