#include<bits/stdc++.h>
// #include "ancient2.h"
#include "grader.cpp"
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
//#define int ll
//#define N
using namespace std;
namespace
{
bitset<1005>f[1005];
int n;
int tot;
}
void qry(int x,int y)
{
for (int i=2;i*i<=x;i++)
if (x%i==0) return;
++tot;
if (tot>1000) return;
int m=x*2;
vector<int>a(m,0),b(m,0);
for (int i=0;i<x;i++)
a[i]=(i+1)%x;
for (int i=x;i<x+x;i++)
a[i]=x+(i+1)%x;
for (int i=0;i<x;i++)
b[i]=(i+1)%x;
for (int i=x;i<x+x;i++)
b[i]=x+(i+1)%x;
b[y]=x+(y+1)%x;
b[x+y]=(y+1)%x;
for (int i=0;i<n;i++)
if (i%x==y) f[tot-1][i]=1;
int o=Query(m,a,b);
if (o<x) f[tot-1][n]=0;
else f[tot-1][n]=1;
// cout<<x<<" "<<y<<" "<<f[tot-1][n]<<" "<<o<<endl;
}
std::string Solve(int N)
{
n=N;tot=0;
for (int i=2;i<=1000;i++)
{
for (int j=(i==2)^1;j<i;j++)
{
qry(i,j);
}
}
for (int i=0;i<n;i++)
{
if (!f[i][i])
{
for (int j=i+1;j<n;j++)
if (f[j][i])
{swap(f[j],f[i]);break;
}
}
// if (!f[i][i])
// {
// cout<<"wtf!! "<<i<<endl;
// }
for (int j=i+1;j<n;j++)
if (f[j][i]) f[j]^=f[i];
}
for (int i=n-1;i>=0;i--)
for (int j=0;j<i;j++)
if (f[j][i]) f[j]^=f[i];
string ans="";
for (int i=0;i<n;i++)
ans+=char('0'+f[i][n]);
// cout<<ans<<endl;
return ans;
}