#pragma comment(linker, "/STACK:102400000,102400000")
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int maxn = 2e5 + 10;
int T, ans, length;
char s[maxn];
struct Palindromic_Tree
{
const static int maxn = 2e5 + 10;
const static int size = 26;
char s[maxn];
int next[maxn][size], fail[maxn], len[maxn], half[maxn], dp[maxn];
int ed, sz, last;
void clear()
{
dp[2] = half[2] = last = fail[1] = fail[2] = 1;
len[2] = (len[1] = -1) + 1;
ed = 0; sz = 3;
for (int i = 0; i < size; i++)
{
next[1][i] = next[2][i] = 0;
}
}
int Node(int length)
{
len[sz] = length;
memset(next[sz], 0, sizeof(next[sz]));
return sz++;
}
int get(int x)
{
while (s[ed] != s[ed - len[x] - 1]) x = fail[x];
return x;
}
void add(char pos)
{
int x = (s[++ed] = pos) - 'A', y = get(last);
if (!(last = next[y][x]))
{
last = next[y][x] = Node(len[y] + 2);
fail[last] = len[last] == 1 ? 2 : next[get(fail[y])][x];
if (!(len[last] & 1))
{
half[last] = half[y];
for (int &i = half[last]; s[ed] != s[ed - len[i] - 1] || len[i] + 2 > len[last] / 2;)
{
i = fail[i];
while ((len[i] >= 0) && (len[i] & 1)) i = fail[i];
}
half[last] = len[half[last]] < 0 ? 2 : next[half[last]][x];
dp[last] = min(dp[y] + 1, len[last] / 2 - len[half[last]] + dp[half[last]] + 1);
ans = min(ans, length - len[last] + dp[last]);
}
}
}
}solve;
int main()
{
scanf("%d", &T);
while (T--)
{
solve.clear();
scanf("%s", s);
ans = length = strlen(s);
for (int i = 0; i < length; i++) solve.add(s[i]);
printf("%d\n", ans);
}
return 0;
}