#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

const int MAXN = 2e5;
char str[MAXN + 10];
pii dp[MAXN + 10][2];

inline int chk(pii &res) {
	return res.fi != -1 && res.se != -1;
}
void upd(int i, int o) {
	if (dp[i - 1][o ^ 1] != mkp(-1, -1))
		dp[i][o] = mkp(dp[i - 1][o ^ 1].fi + 1, dp[i - 1][o ^ 1].se + 1);
	if (dp[i - 1][o] != mkp(0, 0) && dp[i - 1][o] != mkp(-1, -1))
		dp[i][o ^ 1] = mkp(max(dp[i - 1][o].fi - 1, 0), dp[i - 1][o].se - 1);
}

void fk(int i, int o) {
	if (dp[i - 1][o ^ 1] == mkp(-1, -1)) return;
	if (dp[i - 1][o ^ 1] != mkp(0, 0))
		dp[i][o] = mkp(max(dp[i - 1][o ^ 1].fi - 1, 0), dp[i - 1][o ^ 1].se + 1);
	else dp[i][o] = mkp(1, 1);
}

int main() {
//	freopen ("std.in", "r", stdin);
//	freopen ("std.out", "w", stdout);
	int T = read();
	while (T--) {
		scanf("%s", str + 1);
		int n =strlen(str + 1);
		for (int i = 1; i <= n; ++i) {
			dp[i][0] = dp[i][1] = mkp(-1, -1);
			if (str[i] == '0')
				upd(i, 0);
			if (str[i] == '1')
				upd(i, 1);
			if (str[i] == '2') {
				fk(i, 0);
				fk(i, 1);
			}
			if (dp[i][0].fi == 0) {
				dp[i][1].fi = 0;
				dp[i][1].se = max(dp[i][1].se, 0);
			}
			if (dp[i][1].fi == 0) {
				dp[i][0].fi = 0;
				dp[i][0].se = max(dp[i][0].se, 0);
			}
		}
		int ans = n;
		if (dp[n][0].fi != -1) ans = min(ans, dp[n][0].fi);
		if (dp[n][1].fi != -1) ans = min(ans, dp[n][1].fi);
		printf("%d\n", ans);
	}
	return 0;
}
 

answer.code:71:1: error: extended character   is not valid in an identifier
   71 |  
      | ^
answer.code:71:1: error: ‘ ’ does not name a type
   71 |  
      | ^
answer.code: In function ‘int main()’:
answer.code:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |                 scanf("%s", str + 1);
      |                 ~~~~~^~~~~~~~~~~~~~~