Dev Skill “What is that” and Prime

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define high 1000010

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int prime[(high>>6) + 1], prm[(high>>1) +9] , plen=0;

#define setbit(n) (prime[n>>6] |= (1 << ((n >> 1) & 31)))
#define checkbit(n) (prime[n>>6] & (1 << ((n >> 1) & 31)))

void sieve()
{
    LL i,j;

    for(i=3; i*i<high; i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i; j<high; j+=(2*i))
            {
                setbit(j);
            }
        }
    }

    prm[plen++] = 2;

    for(i=3; i<high; i+=2)
    {
        if(!checkbit(i))
        {
            prm[plen++] = i;
        }
    }

    //for(i=0; i<100; i++) cout << prm[i] << " ";
    //cout << prm[plen-1];
}

bool isPrime(LL n)
{
    if(n==2) return true;

    if(!(n&1)) return false;

    //if(n < high) return !checkbit(n);

    for(int i=0; i<plen and prm[i]*prm[i]<=n; i++)
    {
        if(!(n%prm[i])) return false;
    }

    return true;
}

bool isGoldBach(LL n)
{
    LL h , b;
    int i;

    h = n/2;

    for(i=0; i<plen; i++)
    {
        if(prm[i] <= h)
        {
            b = n - prm[i];

            if(isPrime(b))
            {
                if(b + prm[i] == n) return true;
            }
        }
    }

    return false;
}

int main()
{
    sieve();
    int t;
    LL n;
    sf("%d", &t);
    while(t--)
    {
        sf("%lld", &n);

        if(isPrime(n)) pf("1\n");
        else if(isGoldBach(n)) pf("2\n");
        else pf("3\n");
    }

    return 0;
}