#include<bits/stdc++.h>

using namespace std;

int n, m, odd[209], even[209], lft[209], rgt[209];
bool C[209];
map < int, bool > b;
vector < int > v[209];
const int lim = 10000001;
unsigned char cr[(lim + 10) >> 3];

bool pairUp (int nod)
{
    if (C[nod]) return 0;
    C[nod] = 1;
    for (auto i : v[nod])
        if (lft[i] == 0 || pairUp (lft[i]))
        {
            lft[i] = nod, rgt[nod] = i;
            return 1;
        }
    return 0;
}

int maxMatch ()
{
    bool ok = 1;
    while (ok)
    {
        ok = 0;
        for (int i=1; i<=n; i++)
            C[i] = 0;
        for (int i=1; i<=n; i++)
            if (rgt[i] == 0)
                ok |= pairUp (i);
    }
    int ans = 0;
    for (int i=1; i<=n; i++)
        ans += (rgt[i] > 0);
    return ans;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

int N;
scanf ("%d", &N);
for (int i=1; i<=N; i++)
{
    int x;
    scanf ("%d", &x);
    b[x] ^= 1, b[x + 1] ^= 1;
}
for (auto it : b)
    if (it.second)
    {
//        printf ("%d\n", it.first);
        if (it.first & 1) odd[++n] = it.first;
        else even[++m] = it.first;
    }
for (int i=2; i * i<=lim; i++)
    if (cr[i >> 3] & (1 << (i & 7))) ;
    else
    {
        for (int j=i * i; j<=lim; j+=i)
            cr[j >> 3] |= 1 << (j & 7);
    }
for (int i=1; i<=n; i++)
    for (int j=1; j<=m; j++)
    {
        int val = odd[i] - even[j];
        if (val < 0) val = -val;
        if (val <= 2 || (cr[val >> 3] & (1 << (val & 7)))) ;
        else v[i].push_back (j);
    }
int T1 = maxMatch ();
n -= T1, m -= T1;
int T3 = n & 1, T2 = n / 2 + m / 2;
printf ("%d\n", T1 + 2 * T2 + 3 * T3);
return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

There are infinitely many cards, numbered 1, 2, 3, ... Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.

Snuke can perform the following operation repeatedly:

* Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.



Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

Input

Input is given from Standard Input in the following format:


N
x_1 x_2 ... x_N


Output

Print the minimum number of operations required to achieve the objective.

Examples

Input

2
4 5


Output

2


Input

9
1 2 3 4 5 6 7 8 9


Output

3


Input

2
1 10000000


Output

4

### Response

```cpp
#include<bits/stdc++.h>

using namespace std;

int n, m, odd[209], even[209], lft[209], rgt[209];
bool C[209];
map < int, bool > b;
vector < int > v[209];
const int lim = 10000001;
unsigned char cr[(lim + 10) >> 3];

bool pairUp (int nod)
{
    if (C[nod]) return 0;
    C[nod] = 1;
    for (auto i : v[nod])
        if (lft[i] == 0 || pairUp (lft[i]))
        {
            lft[i] = nod, rgt[nod] = i;
            return 1;
        }
    return 0;
}

int maxMatch ()
{
    bool ok = 1;
    while (ok)
    {
        ok = 0;
        for (int i=1; i<=n; i++)
            C[i] = 0;
        for (int i=1; i<=n; i++)
            if (rgt[i] == 0)
                ok |= pairUp (i);
    }
    int ans = 0;
    for (int i=1; i<=n; i++)
        ans += (rgt[i] > 0);
    return ans;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

int N;
scanf ("%d", &N);
for (int i=1; i<=N; i++)
{
    int x;
    scanf ("%d", &x);
    b[x] ^= 1, b[x + 1] ^= 1;
}
for (auto it : b)
    if (it.second)
    {
//        printf ("%d\n", it.first);
        if (it.first & 1) odd[++n] = it.first;
        else even[++m] = it.first;
    }
for (int i=2; i * i<=lim; i++)
    if (cr[i >> 3] & (1 << (i & 7))) ;
    else
    {
        for (int j=i * i; j<=lim; j+=i)
            cr[j >> 3] |= 1 << (j & 7);
    }
for (int i=1; i<=n; i++)
    for (int j=1; j<=m; j++)
    {
        int val = odd[i] - even[j];
        if (val < 0) val = -val;
        if (val <= 2 || (cr[val >> 3] & (1 << (val & 7)))) ;
        else v[i].push_back (j);
    }
int T1 = maxMatch ();
n -= T1, m -= T1;
int T3 = n & 1, T2 = n / 2 + m / 2;
printf ("%d\n", T1 + 2 * T2 + 3 * T3);
return 0;
}

```