#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define el '\n'
#define pii pair<int, int>
const int N = 1e6 + 2;
const int Hnum = 2;
#define pt4 array<int, Hnum>
pt4 mods, bases, pw[N];
bool is_prime(int n)
{
if (n <= 1) return 0;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return 0;
return 1;
}
void pre()
{
random_device rd;
mt19937 mt(rd());
auto rnd = [&] (int l, int r) {return uniform_int_distribution<int>(l, r)(mt);};
for (int i = 0; i < Hnum; i++) bases[i] = rnd(100, 500);
for (int i = 0; i < Hnum; i++)
{
mods[i] = rnd(2e8, 2e9);
while (!is_prime(mods[i])) --mods[i];
}
for (int i = 0; i < Hnum; i++) pw[0][i] = 1;
for (int i = 1; i < N; i++)
for (int j = 0; j < Hnum; j++) pw[i][j] = pw[i-1][j] * 1ll * bases[j] % mods[j];
}
struct Hash
{
vector<pt4> prefix, suffix;
int n;
Hash(string &s)
{
n = s.size();
init_prefix(s);
init_suffix(s);
}
void init_prefix(string &s)
{
prefix.assign(n, {});
pt4 pr{};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < Hnum; j++)
{
pr[j] = (pr[j] * 1ll * bases[j] + s[i]) % mods[j];
}
prefix[i] = pr;
}
}
void init_suffix(string &s)
{
suffix.assign(n, {});
pt4 pr{};
for (int i = n-1; i >= 0; i--)
{
for (int j = 0; j < Hnum; j++)
{
pr[j] = (pr[j] * 1ll * bases[j] + s[i]) % mods[j];
}
suffix[i] = pr;
}
}
pt4 get(int l, int r)
{
if (!l) return prefix[r];
pt4 ret = prefix[r];
for (int i = 0; i < Hnum; i++)
{
ret[i] -= (prefix[l-1][i] * 1ll * pw[r-l+1][i]) % mods[i];
if (ret[i] < 0) ret[i] += mods[i];
}
return ret;
}
pt4 getr(int l, int r)
{
if (r == n-1) return suffix[l];
pt4 ret = suffix[l];
for (int i = 0; i < Hnum; i++)
{
ret[i] -= (suffix[r+1][i] * 1ll * pw[r-l+1][i]) % mods[i];
if (ret[i] < 0) ret[i] += mods[i];
}
return ret;
}
};
void solve()
{
string s; cin >> s;
Hash h(s);
int n = s.size(), l = 0, r = n-1, ans = 0, tmp = 0;
while (2*(l+tmp)+1 < n)
{
if (h.get(l, l+tmp) == h.get(r-tmp, r))
{
ans += 2;
l += tmp+1;
r -= (tmp+1);
tmp = 0;
}
else tmp++;
}
if (2*l != n) ans++;
cout << ans << el;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pre();
int t = 1;
cin >> t;
while (t--) {solve();}
}
