#P665D. Simple Subset
Simple Subset
No submission language available for this problem.
Description
A tuple of positive integers {x1, x2, ..., xk} is called simple if for all pairs of positive integers (i, j) (1 ≤ i < j ≤ k), xi + xj is a prime.
You are given an array a with n positive integers a1, a2, ..., an (not necessary distinct). You want to find a simple subset of the array a with the maximum size.
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it.
The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.
The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.
On the first line print integer m — the maximum possible size of simple subset of a.
On the second line print m integers bl — the elements of the simple subset of the array a with the maximum size.
If there is more than one solution you can print any of them. You can print the elements of the subset in any order.
Input
The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.
The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.
Output
On the first line print integer m — the maximum possible size of simple subset of a.
On the second line print m integers bl — the elements of the simple subset of the array a with the maximum size.
If there is more than one solution you can print any of them. You can print the elements of the subset in any order.
Samples
2
2 3
2
3 2
2
2 2
1
2
3
2 1 1
3
1 1 2
2
83 14
2
14 83