#include <bits/stdc++.h>
using namespace std;

#define N 51000000
unsigned int prime[N / 64];
#define gP(n) (prime[n>>6]&(1<<((n>>1)&31)))
#define rP(n) (prime[n>>6]&=~(1<<((n>>1)&31)))
void sieve()
{
    memset( prime, -1, sizeof( prime ) );

    unsigned int i;
    unsigned int sqrtN = ( unsigned int )sqrt( ( double )N ) + 1;
    for( i = 3; i < sqrtN; i += 2 ) if( gP( i ) )
    {
        unsigned int i2 = i + i;
        for( unsigned int j = i * i; j < N; j += i2 ) rP( j );
    }
}

bool checkPrime (int x) {return (x&1)&&gP(x); }

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    sieve();
    for (int i=1; i<30; ++i)
        cout <<i<<' '<<checkPrime(i)<<endl;
return 0;
}