#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
const int N=1e7+7;
int n,m,o,p[N],t[N],f[N],g[N],ans,cnt,mx,st;char s[N<<1];
void kmp(int n,int *s,int *f)
{
	f[1]=0;
	fo(i,2,n)
	{
		f[i]=f[i-1];
		while(f[i]&&s[f[i]+1]!=s[i]) f[i]=f[f[i]];
		if(s[f[i]+1]==s[i]) f[i]++;
	}
}
void work()
{
	scanf("%s",s+1);n=strlen(s+1);
	fo(i,1,n) cnt+=s[i]=='0';
	if(cnt==0||cnt==n){printf("1\n");return;}
	if((cnt<<1)<n)
	{
		fo(i,1,n) s[i]^=1;
		for(int i=1;i<n-i+1;++i) swap(s[i],s[n-i+1]);
	}
	f[n+1]=0;
	fd(i,n,1) f[i]=f[i+1]+(s[i]=='0'?-1:1);
	mx=-1;st=n;
	fd(i,n,1)
	{
		if(f[i+1]>mx) mx=f[i+1],st=i;
	}
	fu(i,1,st) s[n+i]=s[i];
	fo(i,1,n) s[i]=s[i+st-1];
	fo(i,1,n) printf("%c",s[i]); printf("\n");
	fd(i,n,1)
	{
		if(s[i]=='0')
		{
			if(!(o&1)) o++;
			p[o]++;
			continue;
		}
		if(o&1)
		{
			p[o]--;
			if(!p[o]&&o>1) o--,p[o]++;
			else p[++o]=1,t[o]=0;
			continue;
		}
		t[o]=max(t[o],p[o]);p[o]++;p[o-1]--;
		if(p[o-1]==0&&o>2) t[o-2]=max(t[o-2],t[o]),p[o-2]+=p[o],o-=2;
	}
	fo(i,1,o) if(!(i&1)) ans=max(ans,t[i]);
	m=n+1;
	fo(i,1,o)
	{
		fo(j,1,p[i])
		{
			g[--m]=0;
			if(!(i&1)) g[--m]=1;
		}
	}
	kmp(n,g,f);
	m=f[n];
	while(n%(n-m)) m=f[m];
	printf("%d\n",ans+n-m);
	fo(i,0,n) t[i]=p[i]=0;
	cnt=0;o=0;m=0;ans=0;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--) work();
}