prim997

#include <fstream>
#include <bitset>
#define N 10000001
using namespace std;
bitset <N> prim;
struct SOL
{
    int primul,L;
};
SOL sol[N];

void Ciur()
{
    prim[0]=prim[1]=1; /// Ciurul lui Eratostene
    for(int i=2;i*i<N;++i)
        if(prim[i]==0)
            for(int j=2;i*j<N;++j)
                prim[i*j]=1;
}

void Lungime()
{
    int L=0,Lmax=1,primul=1,primul_ant=1;
    bool schimb_primul=true; /// Permite schimbarea primul_ant
    for(int i=1;i<N;++i)
    {
        if(prim[i]) /// Daca nu e prim
        {
            ++L;
            if(L>Lmax)
            {
                Lmax=L;
                if(schimb_primul)
                    primul_ant=primul,schimb_primul=false;
            }

        }
        else /// Daca e prim
        {
            schimb_primul=true;
            primul=i+1;
            L=0;
        }
        sol[i].primul=primul_ant,sol[i].L=Lmax;
    }
}


int main()
{
    ifstream f("prim997.in");
    Ciur();
    Lungime();
    ofstream g("prim997.out");
    int n;
    f>>n;
    int x;
    for(int i=0;i<n;++i)
    {
        f>>x;
        g<<sol[x].primul<<' '<<sol[x].L<<'\n';
    }
    f.close();
    g.close();
    return 0;
}