MTXN2NT1 - XN2NTQ - Judge Subtask 3, 4

Cho   số nguyên dĆ°ĆĄng            , tìm cách xáşżp nhóm thỏa mãn ďż˝iᝁu kiện sau:
  Mỗi số chỉ �ưᝣc xáşżp vào một nhóm;
  Mỗi nhóm có ďż˝úng 2 số và tổng hai số trong mỗi nhóm �ᝁu là số nguyên tố;
  Số lưᝣng nhóm xáşżp �ưᝣc là nhiᝁu nhẼt.
ví d᝼: Với 8 số nguyên dĆ°ĆĄng 1, 2, 3, 4, 5, 6, 7, 8 ta có cách xáşżp thành 4  nhóm (1,4); (2,5); (3,8); 
(6,7);

Cho n số nguyên dĆ°ĆĄng a1, a2, .... an , tìm cách xáşżp nhóm thỏa mãn ďż˝iᝁu kiện sau:

-  Mỗi số chỉ �ưᝣc xáşżp vào một nhóm;

-  Mỗi nhóm có ďż˝úng 2 số và tổng hai số trong mỗi nhóm �ᝁu là số nguyên tố;

-  Số lưᝣng nhóm xáşżp �ưᝣc là nhiᝁu nhẼt.

ví d᝼: Với 8 số nguyên dĆ°ĆĄng 1, 2, 3, 4, 5, 6, 7, 8 ta có cách xáşżp thành 4  nhóm (1,4); (2,5); (3,8); (6,7);

 

Input

- Dòng �ầu chᝊa số nguyên N.

- Dòng thᝊ 2 chᝊa N số nguyên a1, a2, ... an. (ai<=10^6).

Output

- 1 dòng duy nhẼt ghi số nhóm nhiᝁu nhẼt tìm �ưᝣc

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, các số a1, a2,.. an là hoán vị cᝧa 1, 2, ...n [25 tests]
lĆ°u ý: submit ở ďż˝ây chỉ chẼm Subtask 3 và Subtask 4 thôi, �ᝃ chẼm Subtask 1 và Subtask 2 thì vào ďż˝ây: 
http://www.spoj.com/THPTCBT/problems/MTXN2NTQ/


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.