#include<bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define x first
#define y second
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
typedef long long ll;
int stk[200009];
int sk[200009];
int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		cin>>s;int top=0;
		F(i,0,s.size()-1)
		{
			int u=s[i];
			if(u=='2')
			{
				stk[++top]=2;
				continue;
			}
			if(top&&stk[top]==u-'0') top--;
			else if(top>1&&stk[top-1]==u-'0') top--;
			else stk[++top]=u-'0';
		}
		int top1=0;stk[top+1]=-1;
		F(i,1,top)
		{
			if(stk[i]!=2)
			{
				if(top1&&(sk[top1]==stk[i]||sk[top1]==2)) top1--;
				else sk[++top1]=stk[i];
				continue;
			}
			if(!top1){sk[++top1]=2;continue;}
			if(sk[top1]==2) sk[++top1]=2;
			else
			{
				if(stk[i+1]==2)top1--;
				else sk[++top1]=2;
			}
		}
		int _=0;
		while(sk[top1]==2)top1--,_++;
		cout<<max((_+top1)&1,top1-_)<<'\n';
	}
}