#include <bits/stdc++.h>

void solve() {
	std::string s;
	std::cin >> s;
	
	int l1 = -1, r1 = -1;
	int l2 = -1, r2 = -1;
	if (s[0] == '0') {
		l2 = r2 = 1;
	} else {
		if (s[0] == '1') {
			l1 = r1 = 1;
		} else {
			l1 = r1 = l2 = r2 = 1;
		}
	}
	for (int i = 1; i < s.size(); ++ i) {
		int tl1 = l1, tr1 = r1, tl2 = l2, tr2 = r2;
		if (s[i] == '0') {
			if (tl1 != -1) {
				l2 = tl1 + 1;
			} else {
				l2 = -1;
			}
			if (tr1 != -1) {
				r2 = tr1 + 1;
			} else {
				r2 = -1;
			}
			if (tl2 > 0) {
				l1 = tl2 - 1;
			} else {
				l1 = -1;
			}
			if (tr2 > 0) {
				r1 = tr2 - 1;
			} else {
				r1 = -1;
			}
			if (l1 == 0) {
				l2 = 0;
			}
			if (r1 == 0 && r2 == -1) {
				r2 = 0;
			}
		} else {
			if (s[i] == '1') {
				if (tl2 != -1) {
					l1 = tl2 + 1;
				} else {
					l1 = -1;
				}
				if (tr2 != -1) {
					r1 = tr2 + 1;
				} else {
					r1 = -1;
				}
				if (tl1 > 0) {
					l2 = tl1 - 1;
				} else {
					l2 = -1;
				}
				if (tr1 > 0) {
					r2 = tr1 - 1;
				} else {
					r2 = -1;
				}
				if (l2 == 0) {
					l1 = 0;
				}
				if (r2 == 0 && r1 == -1) {
					r1 = 0;
				}
			} else {
				if (tl1 > 0) {
					l2 = tl1 - 1;
				} else {
					if (tl1 == 0) {
						l2 = 1;
					} else {
						l2 = -1;
					}
				}
				if (tl2 > 0) {
					l1 = tl2 - 1;
				} else {
					if (tl2 == 0) {
						l1 = 1;
					} else {
						l1 = -1;
					}
				}
				if (tr1 != -1) {
					r2 = tr1 + 1;
				} else {
					r2 = -1;
				}
				if (tr2 != -1) {
					r1 = tr2 + 1;
				} else {
					r1 = -1;
				}
				if (l1 == 0 || l2 == 0) {
					l1 = l2 = 0;
				}
				if (r1 == 0 || r2 == 0) {
					if (r1 == -1) {
						r1 = 0;
					} 
					if (r2 == -1) {
						r2 = 0;
					}
				}
			}
		}
		//std::cout << l1 << " " << r1 << " " << l2 << " " << r2 << '\n';
	}
	
	int ans = 1 << 30;
	if (l1 != -1) {
		ans = std::min(ans, l1);
	}
	if (l2 != -1) {
		ans = std::min(ans, l2);
	}
	if (r1 != -1) {
		ans = std::min(ans, r1);
	}
	if (r2 != -1) {
		ans = std::min(ans, r2);
	}
	std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int T;
    std::cin >> T;

    while (T --) {
    	solve();
    }

    return 0;
}