THPT Chuyên Bến Tre

For a positive integer n a1, a2, .... an, sought grouped satisfy the following conditions:

- Each number can only be placed in a group;

- Each group has exactly 2 and the total number of two numbers in each group is prime;

- The number of groups are classified as the most.

example: With 8 positive integers 1, 2, 3, 4, 5, 6, 7, 8 have a classified into 4 groups (1,4); (2.5); (3.8); (6.7);

Input

- The first line contains an integer N.

- 2nd line contains N integers a1, a2, ... an. (a[i] <= 10^6).

Output

- 1 single line group number to find the most

Example

Input:
8
1 2 3 4 5 6 7 8

Output:
4

Subtask 1: n<=10 [25 tests]

Subtask 2: n<=20 [25 tests]

Subtask 3: n<=1000 [25 tests]

Subtask 4: n <= 10 ^ 5, the numbers a1, a2, .. a[n] is a permutation of 1, 2, ... n [25 tests]

Note: here judge subtask 3, 4! go to MTXN2NTQ to judge substack 1, 2.

http://www.spoj.com/problems/MTXN2NTQ/en/