#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 200100
#define ge getchar
#define pu putchar
#define fo(i,a,b) for(int i(a),_E_(b);i<=_E_;++i)
using namespace std;
int a[N],nxt[N],b[N],tot,n,c[N],t,nex[N];
char ch;
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int j;t=n=0;tot=1;j=0;
		memset(nex,0,sizeof nex);
		memset(nxt,0,sizeof nxt);
		for(;(ch=ge())>'Z' || ch<'A';);
		for(;ch>='A' && ch<='Z';ch=ge())a[++n]=ch-65;
		fo(i,2,n){
			while(j && a[j+1]!=a[i])j=nxt[j];
			if(a[j+1]==a[i])++j;nxt[i]=j;
		}
		for(int i=n;i;i=nxt[i])c[++t]=i;
		fo(i,1,t>>1)swap(c[i],c[t+1-i]);
		fo(i,1,c[1]-1)b[i]=0;b[c[1]]=1;b[1]=0;
		int p=0;
		fo(i,2,c[1]){
			while(p && b[i]!=b[p+1])p=nex[p];
			if(b[i]==b[p+1])++p;nex[i]=p;
		}
		fo(i,2,t)if(c[i-1]*2>=c[i]){
			fo(j,c[i-1]+1,c[i]){
				b[j]=b[j-c[i]+c[i-1]];while(p && b[p+1]!=b[j])p=nex[p];
				if(b[p+1]==b[j])++p;nex[j]=p;
			}
		}else{
			fo(j,c[i-1]+1,c[i]-c[i-1]-1){
				b[j]=0;while(p && b[p+1]!=b[j])p=nex[p];
				if(b[p+1]==b[j])++p;nex[j]=p;
			}
			int q(p),zero(1),w(c[i]-c[i-1]);
			while(q){
				if(!b[q+1]){
					if(w%(w-q-1)==0)zero=0;
				}q=nex[q];
			}
			if(!b[q+1]){
				if(w%(w-q-1)==0)zero=0;
			}
			if(zero)b[w]=0;else b[w]=1;
			while(p && b[w]!=b[p+1])p=nex[p];
			if(b[w]==b[p+1])++p;nex[w]=p;
			fo(j,1,c[i-1]){
				int w=c[i]-c[i-1]+j;b[w]=b[j];
				while(p && b[w]!=b[p+1])p=nex[p];
				if(b[w]==b[p+1])++p;nex[w]=p;
			}
		}
		fo(i,1,n)pu(b[i]+48);pu('\n');
	}
	fclose(stdin);fclose(stdout);
	return 0;
}