THPT Chuyên Bến Tre

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/