#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,tp,fail[N];
pair<int,int> st[N];
char a[N],b[N];
void trans(int p){
	static char b[N];
	for(int i=0,j=p;i<n;i++,j=(j+1)%n)b[i]=a[j];
	for(int i=0;i<n;i++)a[i]=b[i];
}
void solve(){
	scanf("%s",a);
	n=strlen(a);
	int c0=0,c1=1;
	for(int i=0;i<n;i++)(a[i]=='0'?c0:c1)++;
	if(c0>c1){
		for(int i=0;i<n;i++)a[i]^=1;
		swap(c0,c1);
	}
	if(c1==n){puts("1");return;}
	int p=n-1;
	for(int i=0;i+1<n;i++)if(a[i]=='0'&&a[i+1]=='1')p=(i+1)%n;
	trans(p);
	printf("%s\n",a);
	int now=0,mn=0;p=0;
	for(int i=0,j;i<n;i=j+1){
		for(j=i;j+1<n&&a[j+1]==a[i];j++);
		if(i<j){
			if(a[i]=='0')now-=j-i;
			else now+=j-i;
			if(now<mn)mn=now,p=(j+1)%n;
		}
	}
	trans(p);
	int mx=0;
	for(int i=0,j;i<n;i=j+1){
		for(j=i;j+1<n&&a[j+1]==a[i];j++);
		if(i==j)continue;
		if(a[i]=='1'){
			st[++tp]=make_pair(i,j);
			continue;
		}
		int l=j-i;
		while(l){
			int x=min(l,st[tp].second-st[tp].first);
			l-=x,st[tp].second-=x;
			mx=max(mx,j-st[tp].second-1>>1);
			if(st[tp].second<=st[tp].first)tp--;
		}
	}
	for(int i=1;i<=n;i++)b[i]=0;
	for(int i=1;i<=tp;i++)
		for(int j=st[i].first+1;j<=st[i].second+1;j++)
			b[j]=1;
	for(int i=2,j=0;i<=n;i++){
		while(j&&b[j+1]!=b[i])j=fail[j];
		if(b[j+1]==b[i])j++;
		fail[i]=j;
	}
	int k=n-fail[n];
	if(n%k)k=n;
	printf("%d\n",mx+k);
}
int main(){
	int T;scanf("%d",&T);
	while(T--)solve();
	return 0;
}