Consider n - f_n , it is the minimum period, let's call it A. It makes a good look on the problem.

You may have a sense of recursive solving the problem as you see we almost minimized the problem in the minimum period. I agree with you, but see more carefully.

//    whoisHussain.org
#include <bits/stdc++.h>
using namespace std;

const int N = 300011;
int f[N],q, g[N],sz; 
bool a[N];
int32_t main(){
        string s;
        int n;
        ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
        cin >> q;
        while( q-- ){
                cin >> s;
                n = s.size(), sz = 0;

                f[0] = f[1] = 0;
                for(int i = 2,j = 0; i <= n; i++){
                        while( j!=0 && s[i-1] != s[j] )
                                j = f[j]; 
                        if( s[i-1]==s[j] ) j++;
                        f[i] = j;
                }

                for(int i = n; i; i = f[i] ) g[sz++] = n-i;
                
                for(int i = sz-1, gg = n, cz = 0;i>-1; cz = gg-g[i], gg = g[i], i--){ 
                        for(int j = 0; j < min(gg-g[i], n-gg); j++) a[ j + g[i] ] = a[ j + gg ];
                        if( gg - g[i] > n - gg && (cz == 0 || (gg - g[i]) % cz == 0) ){ 
                                int j = 0;
                                for(; j < cz; j++)
                                        if( a[j + gg-cz ] != a[ gg + j ] ) break;
                                if( j == cz ) a[gg - 1] = 1 - a[gg + cz - 1]; 
                        }
                        a[g[i]] = 0;
                }
                for(int i = 0; i < n; i++)
                        printf("%d",a[i]),a[i] = 0;
                printf("\n");
        }
}