#include<bits/stdc++.h>
#include "ancient2.h"
#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],tmp;
    int n;
    int st[1005],kmp[1005];
    int tot;
    int len;
}
bool insbl(bitset<1005>now)
{
    for (int i=0;i<n;i++)
        if (now[i])
        {
            if (!f[i][i]) return 1;
            now^=f[i];
        }
    return 0;
}
void ins(bitset<1005>now)
{
    for (int i=0;i<n;i++)
        if (now[i])
        {
            if (!f[i][i]){
                f[i]=now;
                return;
            }
            now^=f[i];
        }
}
void qry(int x,int y)
{
    // for (int i=2;i*i<=x;i++)
    //     if (x%i==0) return;
    for (int i=0;i<=n;i++) tmp[i]=0;
    for (int i=0;i<n;i++)
        if (i%x==y) tmp[i]=1;
    if (!insbl(tmp)) 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;
    int o=Query(m,a,b);
    for (int i=0;i<=n;i++) tmp[i]=0;
    for (int i=0;i<n;i++)
        if (i%x==y) tmp[i]=1;
    if (o<x) tmp[n]=0;
    else tmp[n]=1;
    ins(tmp);
}
std::string Solve(int N)
{
    n=N;tot=0;
    for (int i=0;i<100&&i<n;i++)
    {
        int m=i+3;
        vector<int>a(m,0),b(m,0);
        for (int j=0;j<m;j++)
            a[j]=b[j]=(j+1)%m;
        a[m-1]=m-1,b[m-1]=m-1;
        a[m-2]=m-2,b[m-2]=m-2;
        b[i]=i+2,a[i]=i+1;
        int o=Query(m,a,b);
        if (o==m-2)
        {
            f[i][i]=1;
            f[i][n]=0;
        } else f[i][i]=1,f[i][n]=1;
        tot++;
    }
    for (int i=n-1;i>=n-100&&i>=100;i--)
    {
        f[i][i]=1;
        f[i][n]=0;
        len=0;
        for (int j=i;j<n;j++)
            st[++len]=f[j][n];
        st[len+1]=-1;
        vector<int>a(len+1,0),b(len+1,0);
        if (st[1]==1) b[0]=1;
        else a[0]=1;
        for (int j=1,k=0;j<=len;j++)
        {
            while (k&&st[k+1]!=st[j]) k=kmp[k];
            if (j!=1&&st[k+1]==st[j]) k++;
            kmp[j]=k;
            if (st[j+1]==0) a[j]=j+1;
            else a[j]=a[kmp[j]];
            if (st[j+1]==1) b[j]=j+1;
            else b[j]=b[kmp[j]];
        }
        int o=Query(len+1,a,b);
        if (o!=len) f[i][n]=1;
        tot++;
        // cout<<"!"<<len+1<<" "<<st[1]<<endl;
        // for (auto u:a) cout<<u<<",";cout<<'\n';
        // for (auto u:b) cout<<u<<",";cout<<'\n';
        // cout<<i<<" "<<f[i][n]<<" "<<o<<endl;
    }
    for (int i=2;i<=51;i++)
    {
        for (int j=0;j<i;j++)
        {
            qry(i,j);
        }
    }
    // cout<<tot<<endl;
    // for (int i=0;i<n;i++)
    // {
    //     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;
}