#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
typedef long double ld;
int main()
{
int tt = 1;
cin >> tt;
while (tt--)
{
string a;
cin >> a;
ll n = a.length();
int left = 0, right = n;
vector<int> s(n + 1, 0);
vector<int> p(n + 1, 0);
for (int i = n - 1; i >= 0; i--)
{
s[i] = s[i + 1];
if (a[i] == '1')
++s[i];
}
for (int i = 0; i < n; i++)
{
p[i + 1] = p[i];
if (a[i] == '0')
++p[i + 1];
}
int ans = INT_MAX;
while (left <= right)
{
int mid = left + right;
mid /= 2;
int cnt = 0;
int cnt1 = 0;
for (int i = 0; i < n; i++)
{
ll l = i, r = n - 1, id1 = -1;
while (l <= r)
{
ll m = l + r;
m /= 2;
if (p[m + 1] - p[i] <= mid)
l = m + 1, id1 = m;
else
r = m - 1;
}
if (id1 != -1)
{
int h = cnt + s[id1 + 1];
if (h <= mid)
{
++cnt1;
}
}
if (a[i] == '1')
{
cnt += 1;
}
}
if (cnt <= mid)
++cnt1;
if (cnt1)
{
ans = mid;
right = mid - 1;
}
else
left = mid + 1;
}
cout << ans << "\n";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nIGludAojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CmludCBtYWluKCkKewogICAgaW50IHR0ID0gMTsKICAgIGNpbiA+PiB0dDsKICAgIHdoaWxlICh0dC0tKQogICAgewogICAgICAgIHN0cmluZyBhOwogICAgICAgIGNpbiA+PiBhOwogICAgICAgIGxsIG4gPSBhLmxlbmd0aCgpOwogICAgICAgIGludCBsZWZ0ID0gMCwgcmlnaHQgPSBuOwogICAgICAgIHZlY3RvcjxpbnQ+IHMobiArIDEsIDApOwogICAgICAgIHZlY3RvcjxpbnQ+IHAobiArIDEsIDApOwogICAgICAgIGZvciAoaW50IGkgPSBuIC0gMTsgaSA+PSAwOyBpLS0pCiAgICAgICAgewogICAgICAgICAgICBzW2ldID0gc1tpICsgMV07CiAgICAgICAgICAgIGlmIChhW2ldID09ICcxJykKICAgICAgICAgICAgICAgICsrc1tpXTsKICAgICAgICB9CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBwW2kgKyAxXSA9IHBbaV07CiAgICAgICAgICAgIGlmIChhW2ldID09ICcwJykKICAgICAgICAgICAgICAgICsrcFtpICsgMV07CiAgICAgICAgfQogICAgICAgIGludCBhbnMgPSBJTlRfTUFYOwogICAgICAgIHdoaWxlIChsZWZ0IDw9IHJpZ2h0KQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1pZCA9IGxlZnQgKyByaWdodDsKICAgICAgICAgICAgbWlkIC89IDI7CiAgICAgICAgICAgIGludCBjbnQgPSAwOwogICAgICAgICAgICBpbnQgY250MSA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsbCBsID0gaSwgciA9IG4gLSAxLCBpZDEgPSAtMTsKICAgICAgICAgICAgICAgIHdoaWxlIChsIDw9IHIpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgbGwgbSA9IGwgKyByOwogICAgICAgICAgICAgICAgICAgIG0gLz0gMjsKICAgICAgICAgICAgICAgICAgICBpZiAocFttICsgMV0gLSBwW2ldIDw9IG1pZCkKICAgICAgICAgICAgICAgICAgICAgICAgbCA9IG0gKyAxLCBpZDEgPSBtOwogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgciA9IG0gLSAxOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYgKGlkMSAhPSAtMSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpbnQgaCA9IGNudCArIHNbaWQxICsgMV07CiAgICAgICAgICAgICAgICAgICAgaWYgKGggPD0gbWlkKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgKytjbnQxOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIChhW2ldID09ICcxJykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjbnQgKz0gMTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoY250IDw9IG1pZCkKICAgICAgICAgICAgICAgICsrY250MTsKICAgICAgICAgICAgaWYgKGNudDEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFucyA9IG1pZDsKICAgICAgICAgICAgICAgIHJpZ2h0ID0gbWlkIC0gMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBsZWZ0ID0gbWlkICsgMTsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBhbnMgPDwgIlxuIjsKICAgIH0KfQ==