#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
int get_str(char *S)
{
	int len=1;
	do S[1]=getchar();while(S[1]!='0'&&S[1]!='1');
	do S[++len]=getchar();while(S[len]=='0'||S[len]=='1');
	return len-1;
}
int n;char S[20000010];
int sum[10000010];
int cnt1,cnt0,fl;
pair<int,int> stk[10000010];
int top,typ,cnt,sta,tim;
int nxt[10000010];
void solve()
{
	cnt1=cnt0=fl=top=0;tim=-2;
	n=get_str(S);
	for(int i=1;i<=n;i++)
		if(S[i]=='0') cnt0++;else cnt1++;
	if(cnt1<cnt0)
	{
		reverse(S+1,S+n+1);
		swap(cnt1,cnt0);
		for(int i=1;i<=n;i++) S[i]^=1;
	}
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+(S[i]=='0'?-1:1);
		if(sum[i]<sum[fl]) fl=i;	
	}
	fl++;
	for(int i=1;i<fl;i++) S[n+i]=S[i];
	for(int i=1;i<=n;i++) S[i]=S[fl+i-1];
	for(int i=1;i<=n;)
	{
		sta=i,cnt=0,typ=(S[i]=='1');
		while(i<=n&&S[sta]==S[i]) cnt++,i++;
		cnt-=1;
		if(cnt)
		{
			if(typ) stk[++top]=make_pair(cnt,sta);
			else
			{
				while(1)
				{
					if(stk[top].first<=cnt)
					{
						cnt-=stk[top].first;
						tim=max(tim,(i-1-cnt)-(stk[top].second+1)-1);
						top--;
					}
					else
					{
						stk[top].first-=cnt;
						tim=max(tim,(i-1)-(stk[top].second+stk[top].first+1)-1);
						break;
					}
				}
			}
		}
	}
	for(int i=1,fl=1,typ=1;i<=n;i++,typ^=1)
	{
		if(fl<=top&&stk[top].second==i)
		{
			while(stk[top].first--)
				S[i++]='1';
		}
		S[i]=(typ?'1':'0');
	}
	
	for(int i=2;i<=n;i++)
	{
		int p=nxt[i-1];
		while(p&&S[p+1]!=S[i]) p=nxt[p];
		if(S[p+1]==S[i]) nxt[i]=p+1;
		else nxt[i]=0;
	}
	printf("%d\n",(1+tim/2)+(n-nxt[n]));
}
int main()
{
	int T=Qread();
	while(T--) solve();
	return 0;
}