首先考虑 \(k\) 表示 \(2^k+k-1\le n\) 的最大的 \(k\)，打表猜测最优情况满足：
- 所有长度为 \(k\) 的子串恰好覆盖了全部 \(2^k\) 种不同的长度为 \(k\) 的 01 串。
- 所有长度为 \(k+1\) 的子串互不相同。
考虑规约到图论模型，建立一张有 \(2^k\) 个点的图，点 \(i\) 向 \((2i)\bmod 2^k\) 和 \((2i+1)\bmod 2^k\) 连边，那么问题转化为找到一条长度为 \(n-k\) 的路径满足每个点至少经过一次，且每条边至多经过一次。
考虑首先爆搜出一条哈密顿回路，这部分是 trivial 的，直接大力 DFS + 剪枝即可跑过去，我也不知道为什么，可能可以被证明是线性的。剩余部分肯定是若干个环，因为初始每个点出入度都恰好是 \(2\)，而哈密顿回路会恰好消耗每个点 \(1\) 的入度和出度。因此剩余部分我们就选若干个环凑齐 \(n-k\) 条边即可，如果还有剩余就再选一个环的一部分拼接到路径上去。
const int MAXN=1048576;
int n,lim,seq[MAXN+5],len,vis[MAXN+5],flg,res[MAXN+5],rlen,to[MAXN+5];
bool hav[MAXN+5],mark[MAXN+5];
void clear(){
memset(seq,0,sizeof(seq));len=0;
memset(vis,0,sizeof(vis));flg=0;
memset(res,0,sizeof(res));rlen=0;
memset(hav,0,sizeof(hav));memset(mark,0,sizeof(mark));
}
void dfs(int x){
vis[x]=1;seq[++len]=x;if(len==(1<<lim))return flg=1,void();
if(!vis[(x<<1)&((1<<lim)-1)]){
dfs((x<<1)&((1<<lim)-1));
if(flg)return;
}if(!vis[(x<<1|1)&((1<<lim)-1)]){
dfs((x<<1|1)&((1<<lim)-1));
if(flg)return;
}vis[x]=0;--len;
}
void solve(){
scanf("%d",&n);clear();
if(n==1)return puts("1"),void();
if(n==2)return puts("01"),void();
if(n==3)return puts("010"),void();
if(n==4)return puts("0010"),void();
for(lim=1;(1<<lim)+lim-1<=n;lim++);--lim;dfs(0);
// for(int i=1;i<=len;i++)printf("%d%c",seq[i]," \n"[i==len]);
for(int i=1;i<=len;i++)for(int j=0;j<2;j++)
if(((seq[i]<<1|j)&((1<<lim)-1))!=seq[i%len+1])
to[seq[i]]=(seq[i]<<1|j)&((1<<lim)-1);
int rst=n-((1<<lim)+lim-1),pt=0,pos=0;
for(int i=0;i<(1<<lim);i++)if(!hav[i]){
int siz=0;
for(int j=i;!hav[j];j=to[j])hav[j]=1,++siz;
if(siz>rst){pt=i;break;}
else mark[i]=1,rst-=siz;
}
for(int i=1;i<=len;i++)if(seq[i]==pt)pos=i;
for(int i=1;i<=len;i++){
res[++rlen]=seq[(pos+i-2)%len+1];
if(mark[res[rlen]]){
int tmp=res[rlen],st=res[rlen];
do{tmp=to[tmp];res[++rlen]=tmp;}while(tmp!=st);
}
}
int tmp=pt;while(rlen+lim-1<n)res[++rlen]=tmp,tmp=to[tmp];
for(int i=lim-1;~i;i--)printf("%d",res[1]>>i&1);
for(int i=2;i<=rlen;i++)printf("%d",res[i]&1);
printf("\n");
}
int main(){
freopen("tao.in","r",stdin);freopen("tao.out","w",stdout);
int qu;scanf("%d",&qu);while(qu--)solve();
return 0;
}