#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 998244352
#define Mod 998244353
#define ld double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,val)memset(x,val,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now],v=e[i].to;i;v=e[i=e[i].nxt].to)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#undef ll

#include "tmp.h"

#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = int;
i64 v,n;bool flag;
IV init(i64 N,bool type,i64 p){
    flag=0;n=N;
}

bool mat2[]={0,1,0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1,0,0,1,0};
bool mat[]={
    0,0,1,1,0,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,1,1,1,0,1,1,1,0
    ,0,1,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,0,0,0,1,1,1};
bool guess(ull A,i64 x){
    // i64 c0=0,c1=0;
    if(n==3){
        if(A==0)return 0;
        if(A==1)return 1;
        if(A==2)return 0;
        if(A==3)return 1;
    }
    if(n<=5){
        A&=7;
        if(A==0)return 0;
        if(A==1)return 1;
        if(A==2)return 0;
        if(A==3)return 0;
        if(A==4)return 1;
        if(A==5)return 0;
        if(A==6)return 1;
        if(A==7)return 1;
    }
    if(n==6){
        return mat2[A];
    }
    i64 c1=__builtin_popcount(A);
    if(c1<n/3)return 0;if(c1>2*n/3)return 1;
    A&=63;
    return mat[A];
    // i64 cnt=0,mx=0,mn=0;
    // F(i,0,n-2){
    //     if(A>>i&1)mx=max(mx,++cnt);
    //     else mn=min(mn,--cnt);
    //     if(cnt<0)return 0;
    // }
    // return 1;
    // i64 cnt=0;
    // F(i,0,n-2)putchar((A>>i&1)+'0');puts("");
    // F(i,0,n-2)if((A>>i&1)==(A&1))
    //   cnt++;else break;
    // if(cnt&1)return 0;else return 1;
    // if(!flag){
    // }
    // return v;
}