#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
#define endl '\n'
const int MAX = 5e5 + 5, mod = 1e9 + 7;

void solve(){
    // int n; cin >> n;
    string s; cin >> s;
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; i ++){
        a[i] = s[i] - '0' + 1;
    }
    vector<int> d2(n);
    vector<array<int, 2>> p;
    for (int i = 0, l = 0, r = -1; i < n; i ++ ){
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && (a[i - k - 1] & a[i + k])) k ++;
        d2[i] = k--;
        if (i + k > r){
            l = i - k - 1, r = i + k;
            if (l <= r)
            p.push_back({l, r});
        }
    }
    sort(p.begin(), p.end(), [](array<int, 2> a, array<int, 2> b){
        return a[1] < b[1];
    });
    vector<int> dp(p.size() + 1);
    if (dp.empty()) cout << n << endl;
    else{
        int m = p.size();
        for (int i = 1; i <= m; i ++){
            int lk = 0, rk = i - 1;
            while (lk < rk){
                int mid = (lk + rk + 1) >> 1;
                if (mid == 0 or p[mid - 1][1] < p[i - 1][0]) lk = mid;
                else rk = mid - 1;
            }
            dp[i] = max(dp[i - 1], dp[lk] + p[i - 1][1] - p[i - 1][0] + 1);
        }
        cout << n - dp.back() << endl;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;cin>>T;while(T--)
    solve();
}