首先发现周期和 border 是一一对应的，所以我们就是要构造一个 $01$ 串，使得其 border 长度集合和原串一样。

考虑如何构造，当原串没有 border 的时候，那么我们构造的 $01$ 串就应该是 $n-1$ 的 $0$，然后加上一个 $1$。

然后考虑有 border 怎么做。

设最长 border 的长度为 $len$。

分为两种情况：

• 当 $2len\ge n$，那么我们只用构造出 $s_{1,len}$ 对应的 $01$ 串即可；
• 当 $2len<n$，考虑中间会有一部分的子串还需构造，不妨将其全部设为 $0$，然后 check 一下合不合法，这个可以直接再跑一次 KMP，如果不合法，可以将还要填的子串的最后一个位置设为 $1$，这样就合法了，因为这个 $1$ 就可以截断不合法的 border。

单次时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
  int x=0;bool f=0;char ch=getchar();
  while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
  while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  return f?-x:x;
}
const int Maxn=2e5+5;
char s[Maxn];
int n;
int br[Maxn],ans[Maxn];
int brr[Maxn];
void sol(int len){
	if(len==1){
		ans[1]=0;return;
	}
	if(!br[len]){
		for(int i=1;i<len;i++)ans[i]=0;
		ans[len]=1;return;
	}
	if(br[len]*2>=len){
		sol(br[len]);
		int now=br[len];
		for(int i=len;i>br[len];i--)ans[i]=ans[now--];
		return;
	}
	sol(br[len]);
	int now=br[len];
	for(int i=len;now;i--,now--)ans[i]=ans[now];
	now=br[len];
	for(int i=br[len]+1;i<=len-br[len];i++)ans[i]=0;
	brr[0]=-1;
	for(int i=2;i<=len;i++){
		brr[i]=brr[i-1];
		while(~brr[i]&&ans[brr[i]+1]!=ans[i])brr[i]=brr[brr[i]];
		brr[i]++;
	}
	if(brr[len]!=br[len]){
		ans[len-br[len]]=1;
	}
}
inline void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	br[0]=-1;
	for(int i=2;i<=n;i++){
		br[i]=br[i-1];
		while(~br[i]&&s[br[i]+1]!=s[i])br[i]=br[br[i]];
		br[i]++;
	}
	sol(n);
	for(int i=1;i<=n;i++)putchar(48^ans[i]);puts("");
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();
	while(T--)solve();
	cerr<<"time:"<<clock()/1000.0<<'\n';
	return 0;
}
/*
1
BABBAB
*/

#include <cstdio>
#include <cassert>
#include <iostream>
using namespace std;
const int M = 200005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int T,nxt[M];string s;
int get(string x)
{
	int n=x.length();
	for(int i=2,j=0;i<=n;i++)
	{
		while(j && x[j]!=x[i-1]) j=nxt[j];
		if(x[j]==x[i-1]) j++;
		nxt[i]=j; 
	}
	return nxt[n];
}
string solve(string x)
{
	int t=get(x),n=x.length();
	string y,r;r.resize(n);
	if(t==0)
	{
		if(n==1) return "0";
		for(int i=0;i+1<n;i++) r[i]='0';
		r[n-1]='1';
		return r;
	}
	if(t<(n+1)/2)
	{
		for(int i=0;i<t;i++) y+=x[i];
		string h=solve(y);
		for(int i=0;i<t;i++)
			r[i]=r[n-t+i]=h[i];
		for(int i=t;i<=n-t-1;i++)
			r[i]='0';
		if(get(r)!=t) r[n-t-1]='1';
	}
	else
	{
		t=n-t;
		for(int i=0;i<t;i++) y+=x[i];
		for(int i=n-(n%t);i<n;i++) y+=x[i];
		string h=solve(y);
		for(int i=0;i<n;i++) r[i]=h[i%t];
	}
	return r;
}
void work()
{
	cin>>s;
	cout<<solve(s)<<endl;
}
signed main()
{
	T=read();
	while(T--) work();
}