Breeding Bugs

This year is a good year for North America. 2022 is one of the few years in which no brood of periodical cicadas hatches, so no swarms will destroy the crops in the fields.

Periodical cicadas have a strange property. Their life cycles are highly synchronized, so almost all individuals in a local population emerge in the same year, which causes periodical cicada plagues. Stranger still, their periodicities appear to be prime, such as 13 or 17 years. The most plausible theory so far is that a prime periodicity helps them avoid predators with shorter population cycles, because a brood emergence rarely coincides with a predator's population boost.

Nobody likes cicada plagues, so this prime periodicity is now your problem. You hope that cicadas with non-prime periodicity will be unable to avoid predators, and that cicada plagues will become rarer as a result. To prevent the next plague, you plan to breed different cicada types to create a new type with non-prime periodicity. If you mate a cicada of periodicity $a$ with a cicada of periodicity $b$, you assume the offspring has periodicity $a+b$. You have already captured $n$ cicadas for breeding, but you do not know which ones will mate. So you set some cicadas free, so that the remaining ones can mate in any way they like this year without producing a cicada with prime periodicity. What is the maximum number of cicadas you can keep?

The first line contains a single integer $n$ ($1\leq n<750$), the number of cicadas.

The second line contains $n$ integers $p_1, \ldots, p_n$ ($1\leq p_i<10^7$), where $p_i$ is the periodicity of the $i$th cicada.

Output a single integer, the maximum number of cicadas you can keep.