//Author: Kevin
#include<bits/stdc++.h>
#include"ancient2.h"
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int n=1000;
bitset<1005> bs[1005],bs2[1005];
bool ins(bitset<1005> b)
{
	for(int i=0;i<n;i++)
		if(b[i])
		{
			if(!bs[i][i])
			{
				bs[i]=b;
				return true;
			}
			b^=bs[i];
		}
	return false;
}
int query(int N,int x,int y)
{
	int M=x*2;
	vector<int> A(M),B(M);
	for(int i=0;i<x;i++)
		for(int j=0;j<2;j++)
		{
			A[i*2+j]=((i+1)%x*2+j);
			if(i==y)
				B[i*2+j]=((i+1)%x*2+1-j);
			else
				B[i*2+j]=((i+1)%x*2+j);
		}
	return Query(M,A,B)&1;
}
string Solve(int N)
{
	const int Lim=102;
	int tot=0;
	for(int i=0;i+3<=Lim;i++)
	{
		int M=i+3;
		vector<int> A(M),B(M);
		for(int j=0;j<i;j++)
			A[j]=B[j]=j+1;
		A[i]=i+1;
		B[i]=i+2;
		A[i+1]=B[i+1]=i+1;
		A[i+2]=B[i+2]=i+2;
		int node=Query(M,A,B);
		bitset<1005> b;
		b[i]=bs2[tot][i]=1;
		ins(b);
		bs2[tot++][N]=(node==i+2);
	}
	for(int i=1;i<=N&&tot<N;i++)
		for(int j=0;j<i&&tot<N;j++)
		{
			bitset<1005> b;
			for(int k=0;k<N;k++)
				if(k%i==j)
					b[k]=1;
			if(ins(b))
			{
				bs2[tot]=b;
				bs2[tot++][N]=query(N,i,j);
			}
		}
	for(int i=0;i<N;i++)
	{
		if(!bs2[i][i])
		{
			for(int j=i+1;j<N;j++)
				if(bs2[j][i])
				{
					swap(bs2[i],bs2[j]);
					break;
				}
		}
		for(int j=0;j<N;j++)
			if(i!=j&&bs2[j][i])
				bs2[j]^=bs2[i];
	}
	string ret;
	for(int i=0;i<N;i++)
		ret+=(char)('0'+bs2[i][N]);
	return ret;
}