#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define int long long
#define debug(x) cout<<""#x" = "<< x<<endl;

const int N = 2e5 + 5;
int n, m, k, x, y, T;
int vis[N];
PII idx[N];
int del;
signed ans = 0;
void unions(int l, int r, string& s)
{
	//debug(l);
	//debug(r);
	vector<int>v;
	v.push_back(l);
	v.push_back(r);
	if (l < 0 || r >= s.size())
	{
		return;
	}
	//    idx[r].l=idx[l].l;
	//    idx[l].r=idx[r].r;
	//    if(idx[r].r<s.size()&&idx[l].l>=0)
	//    {
	//        idx[idx[r].r].l=idx[l].l;
	//        idx[idx[l].l].r=idx[r].r;
	//    }
	l = idx[l].first, r = idx[r].second;
	del += 2;
	//cout << del << endl;
	while (l >= 0 && r < s.size())
	{
		if (s[r] == '2')
		{
			break;
		}
		if (s[l] == s[r])
		{
			//debug(l);
			//debug(r);
			//            idx[r].l=idx[l].l;
			//            idx[l].r=idx[r].r;
			del += 2;
			//cout << del << endl;
			v.push_back(l);
			v.push_back(r);
			l = idx[l].first, r = idx[r].second;
			//            if(idx[r].r<s.size()&&idx[l].l>=0)
			//            {
			//                idx[idx[r].r].l=idx[l].l;
			//                idx[idx[l].l].r=idx[r].r;
			//            }
		}
		else
		{
			break;
		}
	}
	//debug(l);
	//debug(r);
	for (auto x : v)
	{
		idx[x].first = l;
		idx[x].second = r;
	}
	idx[l].second = r;
	idx[r].first = l;
	ans += v.size();
}
void solve() {
	string tmp;
	cin >> tmp;
	string s;
	ans = 0;
	stack<char>st;
	for (int i = 0; tmp[i]; i++)
	{
		if (st.empty())
		{
			st.push(tmp[i]);
		}
		else
		{
			if (tmp[i] == st.top())
			{
				st.pop();
			}
			else
			{
				st.push(tmp[i]);
			}
		}
	}
	while (!st.empty())
	{
		s += st.top();
		st.pop();
	}
	reverse(s.begin(), s.end());
	//cout<<s<<endl;
	for (int i = 0; i < s.size(); i++)
	{
		idx[i].first = i - 1;
		idx[i].second = i + 1;
	}
	del = 0;
	for (int i = 0; i < s.size(); i = idx[i].second)
	{
		if (s[i] == '2')
		{
			//debug(i);
			int left = i - del + 1;
			int right = s.size() - i - 1;
			if (left > right)
			{
				unions(idx[i].first, i, s);
			}
			else
			{
				unions(i, idx[i].second, s);
			}
		}
	}
	cout << s.size() - ans << endl;
	//cout << s.size()<< endl;
	//cout << del<< endl;
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int t;
	cin >> t;
	
	while (t--)solve();
	
	return 0;
}