매미 교배

2022년은 북아메리카에 좋은 해다. 2022년은 주기 매미의 어느 무리도 부화하지 않는 몇 안 되는 해이므로, 들판의 작물을 망치는 떼가 나타나지 않는다.

주기 매미에게는 다소 이상한 성질이 있다. 생활 주기가 매우 잘 맞춰져 있어서, 한 지역 개체군의 거의 모든 개체가 같은 해에 나타나고, 그 결과 주기적인 매미 대발생이 일어난다. 더 이상한 점은 이 생활 주기가 13년이나 17년처럼 소수로 보인다는 것이다. 지금까지 가장 유력한 이론은, 소수 주기 덕분에 더 짧은 개체군 주기를 가진 포식자를 피할 수 있다는 것이다. 매미 무리의 출현이 포식자 개체군이 늘어나는 시기와 겹치는 일이 드물기 때문이다.

누구도 매미 대발생을 반기지 않는다. 그래서 이 소수 주기가 이제 여러분의 문제가 된다. 소수가 아닌 주기를 가진 매미는 포식자를 피하지 못하고, 그 결과 매미 대발생이 줄어들기를 바란다. 다음 대발생을 막기 위해, 서로 다른 유형의 매미를 교배해서 소수가 아닌 주기를 가진 새로운 유형을 만들려고 한다. 주기가 $a$인 매미를 주기가 $b$인 매미와 교배하면 자손의 주기가 $a+b$가 된다고 가정한다. 이미 교배에 쓸 매미 $n$마리를 잡았지만, 어느 매미끼리 짝을 짓게 될지는 알 수 없다. 그래서 일부 매미를 풀어 주려고 한다. 남은 매미들이 올해 어떤 방식으로 짝을 짓더라도 소수 주기를 가진 매미가 생기지 않아야 한다. 최대 몇 마리까지 남길 수 있는가?

첫 줄에 매미의 수를 나타내는 정수 $n$ ($1\leq n<750$)이 주어진다.

둘째 줄에는 $n$개의 정수 $p_1, \ldots, p_n$ ($1\leq p_i<10^7$)이 주어진다. $p_i$는 $i$번째 매미의 주기를 나타낸다.

남길 수 있는 매미의 최대 수를 정수 하나로 출력한다.