A tuple of positive integers {x_1, x_2, ..., x_{k}} is called simple if for all pairs of positive integers (i,  j) (1  ≤ i  <  j ≤ k), x_{i}  +  x_{j} is a prime.

You are given an array a with n positive integers a_1,  a_2,  ...,  a_{n} (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.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — 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 b_{l} — 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.


-----Examples-----
Input
2
2 3

Output
2
3 2

Input
2
2 2

Output
1
2

Input
3
2 1 1

Output
3
1 1 2

Input
2
83 14

Output
2
14 83

Difficulty: interview

Starter code:

Solutions:
def main():
    n = int(input())
    l = list(map(int, input().split()))
    seive = [False, True] * max(l)
    a = len(seive)
    for i in range(3, int(a ** .5) + 1, 2):
        if seive[i]:
            for j in range(i * i, a, i):
                seive[j] = False
    i = l.count(1)
    if i:
        res = [1] * i
        for a in l:
            if a > 1 and seive[a + 1]:
                res.append(a)
                break
        if len(res) > 1:
            print(len(res))
            print(*res)
            return
    l0, l1 = [], []
    for a in l:
        if a != 1:
            if a & 1:
                for b in l0:
                    if seive[a + b]:
                        print(2)
                        print(a, b)
                        return
                l1.append(a)
            else:
                for b in l1:
                    if seive[a + b]:
                        print(2)
                        print(a, b)
                        return
                l0.append(a)
    print(1)
    print(l[0])


def __starting_point():
    main()

__starting_point()

def main():
    input()
    l0, l1, ones = [], [], 0
    for a in map(int, input().split()):
        if a == 1:
            ones += 1
        else:
            (l1 if a & 1 else l0).append(a)
    seive = [False, True] * (((max(l0) if l0 else 0) + (max(l1) if l1 else 0)) // 2 + 1)
    a = len(seive)
    for i in range(3, int(a ** .5) + 1, 2):
        if seive[i]:
            for j in range(i * i, a, i):
                seive[j] = False
    if ones:
        res = ['1'] * ones
        for a in l0:
            if a > 1 and seive[a + 1]:
                res.append(str(a))
                break
        if len(res) > 1:
            print(len(res))
            print(' '.join(res))
            return
    for a in l1:
        for b in l0:
            if seive[a + b]:
                print(2)
                print(a, b)
                return
    print(1)
    print(1 if ones else (l0 if l0 else l1)[0])


def __starting_point():
    main()

__starting_point()

from time import time
n = int(input())
a = list(map(int, input().split()))

start = time()

cache = {}


def is_prime(n):
    if n not in cache:
        cache[n] = _is_prime(n)

    return cache[n]


def _is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n % 2 == 0: return False
    if n < 9: return True
    if n % 3 == 0: return False
    r = int(n ** 0.5)
    f = 5
    while f <= r:
        if n % f == 0: return False
        if n % (f + 2) == 0: return False
        f += 6
    return True


s = {}
i = 0
while i < len(a):
    if a[i] > 1 and a[i] in s:
        a.pop(i)
    else:
        s[a[i]] = True
        i += 1

p = [0] * len(a)
for i in range(0, len(a)):
    for j in range(i + 1, len(a)):
        if not is_prime(a[i] + a[j]):
            p[i] += 1
            p[j] += 1

while True:
    mx = max(p)
    if mx == 0:
        break

    mi = p.index(mx)

    for i in range(0, len(a)):
        if i == mi or not is_prime(a[mi] + a[i]):
            p[i] -= 1

    a.pop(mi)
    p.pop(mi)

print(len(a))
print(" ".join(map(str, a)))

#print(time() - start)


import math

N = 2000001
sq = math.floor(N ** 0.5)
isprime = [True] * N
for p in range(2, N):
    if isprime[p]:
        for i in range(p**2, N, p):
            isprime[i] = False

def solve():
    n = int(input())
    A = [int(x) for x in input().split()]
    odd = list([x for x in A if x%2])
    even = list([x for x in A if x%2 == 0])
    k = odd.count(1)
    res = None
    if k > 0:
        for i in even:
            if isprime[i+1]:
                res = [1]*k + [i]
                return res
        if k > 1:
            res = [1]*k
            return res
    if res is None:
        for i in odd:
            for j in even:
                if isprime[i+j]:
                    res = [i, j]
                    return res
    return [A[0]]

res = solve()
print(len(res))
print(' '.join(map(str, res)))


def primes_upto(limit):
    is_prime = [False] * 2 + [True] * (limit - 1) # remove odd numbers
    for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
        if is_prime[n]:
            for i in range(n*n, limit+1, n):
                is_prime[i] = False
    return [i for i, prime in enumerate(is_prime) if prime]

check = set(primes_upto(2*10**6 + 500))
n = int(input())
arr = list(map(int,input().split()))
one_present = False
cnt_ones = 0
for i in arr:
    if i == 1:
        one_present = True
        cnt_ones += 1

num1,num2,prime = 0,0,0
for i in range(n):
    for j in range(n):
        if one_present:
            if cnt_ones > 1:
                if arr[i] + arr[j] in check and arr[i] + 1 in check and arr[j] + 1 in check and arr[i] != 1 and arr[j] != 1:
                    num1 = arr[i]
                    num2 = arr[j]
                if arr[i] + 1 in check and arr[i] != 1:
                    num1 = arr[i]
                if arr[i] in check:
                    prime = arr[i]
            else:
                if arr[i] + arr[j] in check and arr[i] != 1 and arr[j] != 1:
                    num1 = arr[i]
                    num2 = arr[j]
                if arr[i] + 1 in check and arr[i] != 1:
                    num1 = arr[i]
                if arr[i] in check:
                    prime = arr[i]
        else:
            if arr[i] + arr[j] in check:
                num1 = arr[i]
                num2 = arr[j]
            if arr[i] in check:
                prime = arr[i]

if one_present:
    if cnt_ones > 1:
        if num2 == 0:
            if num1 == 0:
                print(cnt_ones)
                for i in range(cnt_ones):
                    print(1, end= ' ')
            else:
                print(cnt_ones + 1)
                for i in range(cnt_ones):
                    print(1, end=' ')
                print(num1, end= ' ')
        else:
            print(cnt_ones + 2)
            for i in range(cnt_ones):
                print(i, end=' ')
            print(num1, end=' ')
            print(num2, end=' ')
    else:
        if num2 == 0:
            if num1 == 0:
                print(1)
                print(1)
            else:
                print(2)
                print('1 '+str(num1))
        else:
            print(2)
            print(str(num1) + ' ' + str(num2))
else:
    if num1 == 0:
        if prime == 0:
            print(1)
            print(arr[0])
        else:
            print(1)
            print(prime)
    else:
        print(2)
        print(str(num1) + ' ' + str(num2))



n = int(input())
L = list(map(int, input().split()))
P = [-1 for _ in range(2000001)]

def premier(n):
    if P[n] >= 0:
        return P[n]
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            P[n] = False
            return False
    P[n] = True
    return True

e = L.count(1)
if n == 1:
    print(1)
    print(L[0])
elif e > 1:
    L.sort()
    i = 1
    while i < n and L[i] == 1:
        i += 1
    u = i
    ok = 0
    while i < n:
        if premier(L[i]+1):
            print(u+1)
            for j in range(u):
                print(1,end=" ")
            print(L[i])
            ok = 1
            break
        i += 1
    if ok == 0:
        print(u)
        for i in range(u):
            print(1,end=" ")
else:
    ok = 0
    for i in range(n-1):  
        for j in range(i+1,n):
            t = premier(L[i]+L[j])
            if t:
                print(2)
                print(str(L[i])+" "+str(L[j]))
                ok = 1
                break
        if ok:
            break
    if ok == 0:
        print(1)
        print(L[0])


#import sys
import math
#sys.stdin = open('in', 'r')
n = int(input())
a = [int(x) for x in input().split()]
#n,m = map(int, input().split())


p1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511]
primes = dict(map(lambda x:(x, True), p1))
def isPrime(v):
    if v in primes:
        return primes[v]
    sqrti = math.sqrt(v)
    for i in range(len(p1)):
        if v % p1[i] == 0:
            primes[v] = False
            return False
        if p1[i] > sqrti:
            break
    primes[v] = True
    return True

done=False
cnt1 = sum(filter(lambda x: x == 1, a))

if cnt1 > 1:
    for i in range(n):
        if a[i] != 1 and isPrime(a[i] + 1):
            done=True
            print(cnt1 + 1)
            print(a[i],end=' ')
            print(str.join(' ', ['1']*cnt1))
            break
    if not done:
        done = True
        print(cnt1)
        print(str.join(' ', ['1']*cnt1))
else:    
    for i in range(n):
        for j in range(n):
            if i != j and isPrime(a[i]+a[j]):
                done = True
                print(2)
                print(f'{a[i]} {a[j]}')
                break
        if done:
            break
    if not done:
        print(1)
        print(a[0])


def isPrime(n):
    if n <= 1: 
        return False
    if n <= 3: 
        return True
    if n % 2 == 0 or n % 3 == 0: 
        return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True

n = int(input())
arr = list(map(int,input().split()))

count = {}

for i in arr:
    try:
        count[i] += 1
    except KeyError:
        count[i] = 1
        
numbers = list(count.keys())
numbers.sort()
a,b = -1,-1
flag = False
for i in range(len(numbers)-1):
    for j in range(i+1,len(numbers)):
        if isPrime(numbers[i]+numbers[j]):
            a = numbers[i]
            b = numbers[j]
            flag = True
            break
    if flag:
        break
        
if a == b and a == -1:
    if numbers[0] == 1 and count[1] > 1:
        print(count[1])
        for i in range(count[1]):
            print(1,end=' ')
        print()
    else:
        print(1)
        print(numbers[0])
elif a == 1:
    print(count[1]+1)
    for i in range(count[1]):
        print(1,end=' ')
    print(b)
else:
    if numbers[0] == 1 and count[1] > 2:
        print(count[1])
        for i in range(count[1]):
            print(1,end=' ')
        print()
    else:
        print(2)
        print(a,b)
    
    
    

import sys


def get_primes(n: int):
    from itertools import chain
    from array import array
    primes = {2, 3}
    is_prime = (array('b', (0, 0, 1, 1, 0, 1, 0)) +
                array('b', (1, 0, 0, 0, 1, 0))*((n-1)//6))

    for i in chain.from_iterable((list(range(5, n+1, 6)), list(range(7, n+1, 6)))):
        if is_prime[i]:
            primes.add(i)
            for j in range(i*3, n+1, i*2):
                is_prime[j] = 0

    return is_prime, primes


n = int(input())
a = list(map(int, input().split()))
is_prime, primes = get_primes(2*10**6)

one_count = a.count(1)
if one_count > 1:
    for i in range(n):
        if a[i] != 1 and is_prime[a[i] + 1]:
            print(one_count + 1)
            print(*([1]*one_count + [a[i]]))
            return
    else:
        print(one_count)
        print(*([1] * one_count))
else:
    for i in range(n):
        for j in range(n):
            if i != j and is_prime[a[i] + a[j]]:
                print(2)
                print(a[i], a[j])
                return
    else:
        print(1)
        print(a[0])