MTXN2NT1 - XN2NTQ - Judge Subtask 3, 4

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/


Added by:Đặng Minh Tiến
Date:2014-12-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-12-17 15:57:24 Con Bò Huyền Thoại
Managers expect spoj.com sympathy for the existence of the second problem. because we have 100 test. but only a maximum of 63 test upload / problem. So we decided to split substack substack 1.2 and 3.4.
Please do sympathy.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.