今年对于北美来说是个好年份。2022年是少数没有周期蝉孵化的年份之一，因此，不会有蝉群破坏田间的庄稼。

一只蝉。图片由 parlansky, Pixabay 提供

这些周期蝉有一种相当奇怪的特性：它们拥有高度同步的生命周期，这意味着当地种群中几乎所有的个体都会在同一年出现，从而导致周期性的蝉灾。更奇怪的是，这些生命周期的周期长度似乎都是质数，例如 13 年或 17 年。目前对此最好的解释是，质数周期能让它们避开生命周期较短的捕食者，因为蝉群的出现很少会与捕食者的种群高峰重合。

但没人喜欢蝉灾，所以这种质数周期现在成了你的难题。你希望非质数周期的蝉将无法再避开捕食者，从而减少蝉灾的发生。因此，为了防止下一次蝉灾，你制定了一个计划：通过培育不同类型的蝉来获得一种具有非质数周期的新类型。如果你将一种周期为 $a$ 的蝉与另一种周期为 $b$ 的蝉进行交配，你假设会得到一种周期为 $a + b$ 的蝉。你已经捕获了 $n$ 只蝉用于培育，但你不知道哪些会交配。因此，你决定放走一些蝉，使得剩下的蝉今年无论以何种方式交配，都不会产生出具有质数周期的蝉。你最多能保留多少只蝉？

输入格式

输入包含： 一行包含一个整数 $n$ ($1 \le n < 750$)，表示蝉的数量。 一行包含 $n$ 个整数 $p_1, \dots, p_n$ ($1 \le p_i < 10^7$)，其中 $p_i$ 表示第 $i$ 只蝉的周期。

输出格式

输出一个整数，表示你能保留的蝉的最大数量。

样例

输入格式 1

8
1 2 3 4 5 6 7 8

输出格式 1

4

输入格式 2

5
7 13 2 2 4

输出格式 2

4