#include "bits/stdc++.h"
 
using namespace std;
 
// GCC Optimizations
#pragma GCC diagnostic ignored "-Wunused-variable" // Ignore unused variable warning
#pragma GCC diagnostic ignored "-Wunknown-pragmas" // Ignore unknown pragmas warning
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
// Macros
#define int long long
#define ll long long
#define ld long double
 
// Constants
constexpr long long SZ = 1e5 + 7;
constexpr long long inf = 1e18;
constexpr long long mod = 1e9 + 7;
constexpr long long MOD = 998244353;
constexpr long double PI = 3.141592653589793238462;
 
// Macros
#define vt vector // not cool
#define pb push_back
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()
 
#define each(x, a) for (auto &x: a)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define forr(i, n) for (int i = n; i >=0; --i)
 
#define fi first
#define se second
#define endl '\n'
 
#define setbits(X) __builtin_popcountll(X)
#define fix(X) fixed << setprecision(X)
#define mem0(X) memset((X), 0, sizeof((X)))
#define mem1(X) memset((X), -1, sizeof((X)))
 
// Debug Functions
void __print(int x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << x; }
void __print(const char *x) { cerr << x; }
void __print(const string &x) { cerr << x; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) {cerr << (f++ ? ", " : ""); __print(i);} cerr << "}";}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) {cerr << ", ";} _print(v...);}
 
#ifdef ambarsariya
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define  dbg(x...)
#endif
 
// Min Max
template<class T>
bool amin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<class T>
bool amax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
// Operator overloads <<, >>
template<typename T1, typename T2> // cin >> pair
istream &operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
template<typename T> // cin >> vector
istream &operator>>(istream &istream, vector<T> &v) { for (auto &it : v) { cin >> it; } return istream; }
template<typename T1, typename T2> // cout << pair
ostream &operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector
ostream &operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) { cout << it << " "; } return ostream; }
 
// Google
int tc_cnt = 1;
#define ns()               cout << "Case #" << tc_cnt ++ << ": ";
 
// Power under mod (a ^ b) % mod
int modpow(int a, int b, int m = mod) {
    a = a & m; int ans = 1;
    while (b) {
        if (b & 1) { ans = (ans * a) % m; }
        b = b >> 1; a = (a * a) % m;
    }
    return ans;
}
 
// Inverse Mod (1 / a) % mod
int modinv(int a, int m = mod) { return modpow(a, m - 2); }
 
// Modular Arithematic
int modadd(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
int modsub(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
int modmul(int a, int b, int m = mod) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
int moddiv(int a, int b, int m = mod) { a = a % m; b = b % m; return (modmul(a, modinv(b, m), m) + m) % m; }
 
// GCD
int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }
 
// LCM
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
 
// Directions
const int dx[8] = {0, 1, -1, 0, -1, -1, 1, 1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
 
int mul(int a, int b) {
    int ans = 0;
    while (b) {
        if (b & 1) {
            ans += a;
        }
        b = b >> 1;
        a += a;
        if (a > inf) {
            a = inf;
        }
        if (ans > inf) {
            ans = inf;
        }
    }
    return ans;
}
 
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.first==b.first){
        return a.second<b.second;
    }
    return a.first<b.first;
}
vector<int> cnt;
class Compare
{
public:
    bool operator() (pair<int,int> a, pair<int,int> b)
    {
        if(a.first==b.first){
            return cnt[a.second]>cnt[b.second];
        }
        return a.first>b.first;
    }
};
// solution
void solve(){
	// taking in the input
    string s;
    cin>>s;
    cnt.clear();
    string s1="";
    int count=0;
    // here i am counting the number of zeros and pushing it into the array as it is better to remove all the contnous zeros than
    // removing only one zero
    for(int i=0;i<s.length();i++){
        if(s[i]=='0'){
            count++;
        }
        else{
            if(count>0)cnt.push_back(count);
            count=0;
        }
 
    }
    if(count>0)cnt.push_back(count);
    // here im storing the number of zeros in count variable
    count=accumulate(cnt.begin(),cnt.end(),(ll)0);
    int n=s.length();
    // here i am compressing the string to remove consequent zeros and replacing it with only 1 zero
    for(int i=0;i<n;){
        if(s[i]=='1'){
            s1+='1';
            i++;
        }
        else{
            s1+='0';
            while(i<n and s[i]=='0')i++;
        }
    }
    s=s1;
    n=s.length();
    int cz=0;
    int c=0;
    // here basically im taking a priority queue and adding in it how many ones to get to this zero by going from left and right and storing the min in it
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>> > q;
    vector<int> v;
    for(int i=0;i<n;i++){
        if(s[i]=='0'){
            v.push_back(c);
            cz++;
            c=0;
        }
        else{
            c++;
        }
    }
    c=0;
    int z=0;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='0'){
            z++;
            v[cz-z]=min(v[cz-z],c);
            c=0;
            q.push({v[cz-z],cz-z});
        }
        else{
            c++;
        }
    }
    // the worst ans is the number of zeros present
    int ans=count;
    // sum is to count the number of ones removes
    int sum=0;
    // while q is not empty
    while(!q.empty()){
    	// removing the min ones
        sum+= (q.top().first);
        // removing the zeros after this ones
        count-=cnt[q.top().second];
        q.pop();
        // calculating the ans
        ans=min({ans,max(sum,count)});
    }
    cout<<ans<<endl;
   
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}