#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fir first
#define sec second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
string query(vector<int>);
void answer(string);
const int MAXN=120;
struct DSU{
    int fa[MAXN],sz[MAXN]; vector<int> vec[MAXN];
    void init(int n){
        iota(fa+1,fa+n+1,1),fill_n(sz+1,n,1);
        RNG(i,1,n) vec[i]={i};
    }
    int find(int u){ return fa[u]==u?u:fa[u]=find(fa[u]); }
    void merge(int u,int v){
        if((u=find(u))!=(v=find(v))) fa[v]=u,sz[u]+=sz[v],vec[u].insert(vec[u].end(),vec[v].begin(),vec[v].end()),vec[v].clear();
    }
} dsu;
bool vis[MAXN][MAXN];
void solve(int n,char){
    if(n==1){ answer("0"); return; }
    dsu.init(n);
    auto done=[n](){
        string ans(n,'0');
        RNG(i,1,n){
            if(dsu.sz[dsu.find(i)]*2>n) ans[i-1]='1';
        }
        answer(ans);
    };
    RNG(_,1,10){
        vector<int> all,P(n); vector<pii> Q;
        RNG(i,1,n){
            if(dsu.find(i)==i){
                all.push_back(i);
                if(dsu.sz[i]*2>n){ done(); return; }
            }
        }
        auto add=[&P](int u,int v){ Q.push_back({u,v}),P[u-1]=v,P[v-1]=u; }
        RNG(p,0,int(all.size())-1){
            RNG(q,p+1,int(all.size())-1){
                int i=all[p],j=all[q];
                if(!vis[i][j]) continue;
                bool flag=0;
                for(int u:dsu.f[i]){
                    for(int v:dsu.f[j]){
                        if(P[u-1]||P[v-1]) continue;
                        add(u,v);
                        flag=1; break;
                    }
                    if(flag) break;
                }
            }
        }
        auto res=query(P);
        for(auto [i,j]:Q){
            if(res[i-1]=='1'&&res[j-1]=='1') dsu.merge(i,j);
            else vis[i][j]=1;
        }
        for(int i:P){
            for(int u:dsu.f[i]){
                RNG(v,1,n) vis[i][dsu.find(v)]|=vis[u][v];
            }
        }
    }
    done();
}
#ifdef _LOCAL_
#include "grader.cpp"
int main(){
#if 0
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
    freopen("safpar.in","r",stdin);
    freopen("safpar.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
}
#endif
#else
#include "silent.h"
#endif