#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;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIE4gNTEwMDAwMDAKdW5zaWduZWQgaW50IHByaW1lW04gLyA2NF07CiNkZWZpbmUgZ1AobikgKHByaW1lW24+PjZdJigxPDwoKG4+PjEpJjMxKSkpCiNkZWZpbmUgclAobikgKHByaW1lW24+PjZdJj1+KDE8PCgobj4+MSkmMzEpKSkKdm9pZCBzaWV2ZSgpCnsKICAgIG1lbXNldCggcHJpbWUsIC0xLCBzaXplb2YoIHByaW1lICkgKTsKCiAgICB1bnNpZ25lZCBpbnQgaTsKICAgIHVuc2lnbmVkIGludCBzcXJ0TiA9ICggdW5zaWduZWQgaW50IClzcXJ0KCAoIGRvdWJsZSApTiApICsgMTsKICAgIGZvciggaSA9IDM7IGkgPCBzcXJ0TjsgaSArPSAyICkgaWYoIGdQKCBpICkgKQogICAgewogICAgICAgIHVuc2lnbmVkIGludCBpMiA9IGkgKyBpOwogICAgICAgIGZvciggdW5zaWduZWQgaW50IGogPSBpICogaTsgaiA8IE47IGogKz0gaTIgKSByUCggaiApOwogICAgfQp9Cgpib29sIGNoZWNrUHJpbWUgKGludCB4KSB7cmV0dXJuICh4JjEpJiZnUCh4KTsgfQoKaW50IG1haW4gKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwogICAgc2lldmUoKTsKICAgIGZvciAoaW50IGk9MTsgaTwzMDsgKytpKQogICAgICAgIGNvdXQgPDxpPDwnICc8PGNoZWNrUHJpbWUoaSk8PGVuZGw7CnJldHVybiAwOwp9