/*

    LibreOJ #526. 「LibreOJ β Round #4」子集

    考虑一下，若两个数奇偶性相同

    若同为奇数, 那加1后就是偶数, gcd的乘积就一定不是1

    偶数相同

    那么我们把原数中的偶数分为一个集合，奇数分为一个集合

    把互相之间不符合要求的连边

    那么问题就转化为了二分图求最大独立集

*/

#include <cstdio>

#include <iostream>

#include <queue>

#include <cstring>

const int BUF = ;

char Buf[BUF], *buf = Buf;

#define INF 1e9

inline void read (long long &now)

{

    for (now = ; !isdigit (*buf); ++ buf);

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

}

#define Max 600

struct E { E *n, *r; int v, f; };

E *list[Max], poor[Max * ], *Ta = poor;

int S, T;

class Flow_Type

{

    private :

        int d[Max];

        bool Bfs (int S, int T)

        {

            memset (d, -, sizeof d); d[S] = ;

            std :: queue <int> Queue; int now; E *e;

            for (Queue.push (S); !Queue.empty (); Queue.pop ())

            {

                now = Queue.front ();

                for (e = list[now]; e; e = e->n)

                    if (d[e->v] == - && e->f)

                    {

                        d[e->v] = d[now] + ;

                        if (e->v == T) return true;

                        Queue.push (e->v);

                    }

            }

            return d[T] != -;

        }

        int Flowing (int now, int F)

        {

            if (now == T || !F) return F;

            int res = , pos; E *e;

            for (e = list[now]; e; e = e->n)

            {

                if (d[e->v] != d[now] +  || !e->f) continue;

                pos = Flowing (e->v, e->f < F ? e->f : F);

                if (pos)

                {

                    F -= pos, res += pos, e->f -= pos, e->r->f += pos;

                    if (!F) return res;

                }

            }

            if (res != F) d[now] = -;

            return res;

        }

    public :

        inline void In (int u, int v)

        {

            ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta, Ta->f = ;

            ++ Ta, Ta->v = u, Ta->n = list[v], list[v] = Ta, Ta->f = ;

            list[u]->r = list[v], list[v]->r = list[u];

        }

        int Dinic (int S, int T)

        {

            int Answer = ;

            for (; Bfs (S, T); Answer += Flowing (S, INF));

            return Answer;

        }

};

Flow_Type F;

long long key[Max];

long long Gcd (long long a, long long b) { return !b ? a : Gcd (b, a % b); }

int Main ()

{

    fread (buf, , BUF, stdin);

    long long N; read (N); S = N + , T = N + ;

    register int i, j;

    for (i = ; i <= N; ++ i)

    {

        read (key[i]);

        if (key[i] & ) F.In (i, T);

        else F.In (S, i);

    }

    for (i = ; i <= N; ++ i)

    {

        if ((key[i] & ) == )

            for (j = ; j <= N; ++ j)

                if (key[j] & )

                    if (Gcd (key[i], key[j]) ==  && Gcd (key[i] + , key[j] + ) == )

                        F.In (i, j);

    }

    printf ("%d", N - F.Dinic (S, T));

    return ;

}

int ZlycerQan = Main ();

int main (int argc, char *argv[]) {;}