#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve () {
    string s;
    cin >> s;

    const int n = s.size ();

    if (n == 1) {
        cout << 0 << '\n';
        return;
    }

    vector <pair <int, char>> a;
    for (auto c : s) {
        if (a.empty ()) {
            a.push_back ({1, c});
        } else {
            if (c == a.back ().second) {
                a.back ().first ++;
            } else {
                a.push_back ({1, c});
            }
        }
    }

    if (a.size () == 1) {
        cout << n / 2 << '\n';
        return;
    }

    vector <pair <int, char>> b;
    b.push_back (a.back ());

    const int m = a.size ();

    int ans = 0;
    for (int i = 0; i < m; i ++) {
        ans += a[i].first / 2;
    }

    int minn = ans;

    for (int i = 0; i < m; i ++) {
        while (a[i].first --) {
            ans -= (a[i].first & 1);
            if (a.back ().second != a[i].second) {
                a.push_back ({1, a[i].second});
            } else {
                ans -= a.back ().first / 2;
                a.back ().first ++;
                ans += a.back ().first / 2;
            }
            minn = min (minn, ans);
            // cerr << i << " " << ans << '\n';
        }
    }

    cout << minn << '\n';
}

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    cin >> T;

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

    return 0;
}