// Author: Lech Duraj

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cassert>

#define dprintf(...)
//#define dprintf(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

const int maxn = 100*1000;
const int maxp = 3*maxn+1;

int pal[maxn];
int who[maxn];

int middle[maxp];
int radius[maxp];
vector<int> link[maxp];

vector<int> endq[maxn];
vector<int> events[maxn];

int shorter[maxp];
int half[maxp];

int dp[maxp],dph[maxp];

string A;
int pc;
int n;

int trim(int node, int x, int s=0)
{
    if (x==0)
        return node;
    if ( x%(1<<(s+1)) != 0)
    {
        node = link[node][s];
        x -= (1<<s);
    }    
    return trim(node,x,s+1);
}

void manacher()
{
    int f = 0;
    pal[0] = 0;
    who[0] = 0;
    middle[0] = 0;
    radius[0] = 0;
    pc = 1;
    for(int i=1; i<n; i++)
    {
        who[i] = 0;
        if (f+pal[f]>i)
        {
            int j = f - (i - f);
            who[i] = who[j];
            pal[i] = pal[j];
            int over = i+pal[i]-f-pal[f];
            if (over>0)
            {
                pal[i] -= over;
                who[i] = trim(who[i],over);
            }
        } 
        else
            pal[i] = 0;
        while(i+pal[i]<n && i-pal[i]>0 && A[i+pal[i]]==A[i-pal[i]-1])
        {
            pal[i]++;
            f = i;
            
            middle[pc] = i;
            radius[pc] = pal[i];
            link[pc].clear();
            link[pc].push_back(who[i]);
            int q = 1;
            while((1 << q) <= radius[pc])
            {
                link[pc].push_back(link[link[pc][q-1]][q-1]);
                q++;
            }
            who[i] = pc;
            pc++;
        }
    }
}

int query(int i, set<int> &S, int x)
{
    auto t = S.lower_bound(x+1);
    if (t!=S.begin())
    {
        t--;
        int over = i - (*t - pal[*t]);
        return trim(who[*t], over);
    }
    else
        return 0;
}

int main()
{
    int TT;
    cin >> TT;
    while(TT--)
    {
        cin >> A;
        n = A.length();
        manacher();
        for(int i=0; i<n; i++)
            endq[i].clear();
        for(int q=1; q<pc; q++)
            endq[middle[q]-radius[q]].push_back(q);
        for(int i=0; i<n; i++)
            events[i].clear();
        for(int i=1; i<n; i++)
            if (pal[i]>0)
                events[i-pal[i]].push_back(i);
        set<int> S;
        
        for(int i=0; i<n; i++)
        {
            if (S.find(i)!=S.end())
                S.erase(i);
            for(int e : events[i])
                S.insert(e);
            for(int q : endq[i])
            {
                shorter[q] = query(i,S,middle[q]-1);
                half[q] = query(i,S,middle[q]-radius[q]+radius[q]/2);
            }
        }

        dp[0] = 0;
        dph[0] = 0;
        for(int q = 1; q < pc; q++)
        {
            dph[q] = dph[link[q][0]]+1;
            dph[q] = min(dph[q],dp[half[q]]+radius[q]-2*radius[half[q]]);
            
            dp[q] = dp[link[q][0]]+2;            
            dp[q] = min(dp[q],dph[q]+1);
            dp[q] = min(dp[q],dp[shorter[q]]+2*radius[q]-2*radius[shorter[q]]);            
        }
        
        int best = n;
        for(int q = 0; q < pc; q++)
            best = min(best, n - 2*radius[q] + dp[q]);
        cout << best << endl;
    }
}