#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.size();
        vector<int>f(n+2),g(n+2);
        for(int i=2,j=1;i<=n;i++)
        {
            if(s[i-1]!=s[j-1])j=i;
            f[i]=f[j-1]+(i-j+1)/2;
        }
        for(int i=n-1,j=n;i;i--)
        {
            if(s[i-1]!=s[j-1])j=i;
            g[i]=g[j+1]+(j-i+1)/2;
        }
        int l=1,r=n;
        while(l<n&&s[l]==s[0])
            l++;
        while(r>1&&s[r-2]==s[n-1])
            r--;
        int res=f[n];
        for(int i=1;i<n;i++)
        {
            int cur=f[i]+g[i+1];
            if(s[0]==s[n-1])
            {
                int x=min(i,l),y=min(n-i,n-r+1);
                if(x%2==1&&y%2==1)cur++;
            }
            res=min(res,cur);
        }
        cout<<res<<endl;
    }
    return 0;
}