#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
const int N=2e5+50;
int ch[N][12],Len[N],par[N];
int pos[N],mark[N];
int End,tot;
int New() {
    ++tot;
    Len[tot]=par[tot]=mark[tot]=0;
    pos[tot]=-1;
    memset(ch[tot],0,sizeof(ch[tot]));
    return tot;
}
void Extend(int c,int _pos) {
    int p=End;End=New();Len[End]=Len[p]+1;mark[End]=1;pos[End]=_pos;
    for(; p && !ch[p][c]; p=par[p]) ch[p][c]=End;
    if(!p) par[End]=1;
    else {
        int x=ch[p][c];
        if(Len[p]+1==Len[x]) par[End]=x;
        else {
            int y=New();Len[y]=Len[p]+1;
            memcpy(ch[y],ch[x],sizeof(ch[x]));
            par[y]=par[x];par[End]=par[x]=y;
            for(; ch[p][c]==x; p=par[p]) ch[p][c]=y;
        }
    }
}
vector<int> E[N];
void dfs1(int x) {
    for(auto y: E[x]) {
        dfs1(y);
        if(pos[x]==-1) {
            pos[x]=pos[y];
        }
    }
}
string s;
int cnt[12][12];
int deg[12];
int res=0;
int ans[N];
void dfs2(int x) {
    vector<int> vec;
    // cerr << x << ' ' << pos[x] << ' ' << Len[x] << endl;
    for(auto y: E[x]) vec.push_back(s[pos[y]+Len[x]]-'a');
    for(auto y: E[x]) {
        int u=s[pos[y]+Len[x]]-'a';
        for(auto v: vec) if(v!=u) cnt[v][u]++;
        dfs2(y);
        for(auto v: vec) if(v!=u) cnt[v][u]--;
    }
    if(mark[x]) {
        ans[pos[x]]=0;
        if(vec.size()) return ;
        queue<int> Q;
        FOR(i,0,11) deg[i]=0;
        FOR(i,0,11) FOR(j,0,11) if(cnt[i][j]) ++deg[j];
        FOR(i,0,11) if(deg[i]==0) Q.push(i);
        while(!Q.empty()) {
            int i=Q.front();
            Q.pop();
            FOR(j,0,11) if(cnt[i][j]) {
                if(!--deg[j]) Q.push(j);
            }
        }
        FOR(i,0,11) if(deg[i]) return ;
        ans[pos[x]]=1;
        return ;
    }
}
void solve() {
    tot=0;
    End=New();
    cin >> s;
    DOR(i,s.size()-1,0) Extend(s[i]-'a',i);
    FOR(i,1,tot) E[i].clear();
    FOR(i,2,tot) E[par[i]].push_back(i);
    dfs1(1);
    res=0;
    dfs2(1);
    FOR(i,0,s.size()-1) cout << ans[i];
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}