#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=2000005;
int T,n,nxt[N];
char s[N],t[N];
int main(){
	rd(T);
	while(T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		if(count(s+1,s+n+1,'1')<count(s+1,s+n+1,'0')){
			rep(i,1,n)s[i]^=1;
			reverse(s+1,s+n+1);
		}
		int cur=0,ret=0;
		rep(i,1,n){
			cur=max(cur+(s[i]=='0'?1:-1),0);
			ret=max(ret,cur);
		}
		rep(i,1,n){
			cur=max(cur+(s[i]=='0'?1:-1),0);
			ret=max(ret,cur);
		}
		int todo=0,last=0;
		rep(i,1,n){
			if(s[i]=='0')++todo;
			if(todo>0){
				if(last==1){
					last=0;
					--todo;
				}else{
					last=1;
				}
			}else{
				last=1;
			}
		}
		rep(i,1,n){
			if(s[i]=='0')++todo;
			if(todo>0){
				if(last==1){
					last=0;
					t[i]='0';
					--todo;
				}else{
					last=1;
					t[i]='1';
				}
			}else{
				last=1;
				t[i]='1';
			}
		}
		/*rep(i,1,n)putchar(t[i]);
		puts("");*/
		nxt[0]=nxt[1]=0;
		int j=0;
		rep(i,2,n){
			while(j&&t[i]!=t[j+1])j=nxt[j];
			if(t[i]==t[j+1])++j;
			nxt[i]=j;
		}
		printf("%d\n",n-nxt[n]+max(0,ret-1));
	}
	return 0;
}