#include <bits/stdc++.h>
#define ll long long
#define mx 1000007
using namespace std;
bool ok[mx];
void sieve()
{
ok[0]= ok[1]= 1;
for( int i=2;i<mx;i++ )
{
if(ok[i])
continue;
for( int j=i*2;j<mx;j+=i )
ok[j]= 1;
}
}
int main()
{
sieve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbXggMTAwMDAwNwp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKYm9vbCBva1tteF07Cgp2b2lkIHNpZXZlKCkKewogICAgb2tbMF09IG9rWzFdPSAxOwoKICAgIGZvciggaW50IGk9MjtpPG14O2krKyApCiAgICB7CiAgICAgICAgaWYob2tbaV0pCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIGZvciggaW50IGo9aSoyO2o8bXg7ais9aSApCiAgICAgICAgICAgIG9rW2pdPSAxOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIHNpZXZlKCk7Cn0=