#include"bits/stdc++.h"
#include <typeindex>
using namespace std;
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
string t_case() { static int tc; return "Case " + to_string(++tc) + ':'; }
#define TEM template <class... T>
TEM istream& operator>>(istream& in, pair<T...>& p) { return in >> p.first >> p.second; }
TEM ostream& operator<<(ostream& out, const pair<T...>& p) { return out << '(' << p.first << ", " << p.second << ')'; }
#define def_in(cont) TEM istream& operator>>(istream& in, cont<T...>& A) { for (auto& a : A) in >> a; return in; }
#define def_out(cont) TEM ostream& operator<<(ostream& out, const cont<T...>& A) { int i = 0; auto it = A.begin(); while (it != A.end()) out << &" "[!i++] << *it++; return out; }
def_in(vector) def_in(deque) def_out(vector) def_out(deque) def_out(set) def_out(map) def_out(multiset)
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T){cerr << ' ' << H; dbg_out(T...);}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
// find_by_order(k): Returns the k-th smallest element (0-indexed).
// order_of_key(x): Returns how many elements are strictly smaller than x.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
TEM using ordered_set = tree<T..., null_type, less<T...>, rb_tree_tag, tree_order_statistics_node_update>;
def_out(ordered_set)
TEM istream& c_in(T&... args) { return ((cin >> args), ...); }
TEM ostream& c_out(const T&... args) { int i = 0; return ((cout << &" "[!i++] << args), ...) << '\n'; }
ostream& c_out(bool b) { return c_out(b ? "YES" : "NO"); }
#ifdef DEBUG
TEM ostream& c_err(const T&... args) { int i = 0; return ((cerr << &" "[!i++] << args), ...) << '\n'; }
#else
#define c_err(...)
#endif
#define d_bug(args...) c_err(#args, '=', args)
typedef long long ll;
typedef unsigned long long ull;
#define int ll
const int MOD = 1000000007;
const int inf = 1e18;
// POLYHASH STRUCT
// A complete library for String Hashing in Competitive Programming
// ---------------------------------------------------------
struct PolyHash {
// --- 1. Constants (The Math Setup) ---
static const ll M1 = 1e9 + 7;
static const ll M2 = 1e9 + 9;
// static const ll M1 = 1999999973; // A less common large prime
// static const ll M2 = 2147483647; // 2^31 - 1, another great prime
static const ll P1 = 257;
static const ll P2 = 263;
// --- 2. Static Cache (Shared Memory) ---
// Powers of P are computed once and shared by all instances.
static vector<ll> pow1;
static vector<ll> pow2;
// --- 3. Instance Variables (Specific to THIS string) ---
vector<ll> h1, h2; // Forward prefix hashes
vector<ll> rh1, rh2; // Reverse prefix hashes
// for int change this S
string S; // The original string
int n; // Length of the string
// --- 4. Constructor ---
// for int change this S
PolyHash(string s) : S(s), n(s.size()) {
// STEP A: Precompute Powers if needed
while ((int)pow1.size() <= n) {
pow1.push_back((pow1.back() * P1) % M1);
pow2.push_back((pow2.back() * P2) % M2);
}
// STEP B: Resize Arrays
h1.resize(n + 1, 0);
h2.resize(n + 1, 0);
rh1.resize(n + 1, 0);
rh2.resize(n + 1, 0);
// STEP C: Compute Forward Hashes
for (int i = 0; i < n; ++i) {
// 1. Normalize the value to be positive and within modulo range
// For string
int val1 = (s[i]-'a'+1);
int val2 = (s[i]-'a'+1);
// for vector<int>
// int val1 = (s[i] % M1 + M1) % M1 + 1;
// int val2 = (s[i] % M2 + M2) % M2 + 1;
h1[i + 1] = (h1[i] * P1 + val1) % M1;
h2[i + 1] = (h2[i] * P2 + val2) % M2;
}
// STEP D: Compute Reverse Hashes
for (int i = 0; i < n; ++i) {
// 1. Normalize the value to be positive and within modulo range
// For string
int val1 = (s[n-1-i]-'a'+1);
int val2 = (s[n-1-i]-'a'+1);
// for vector<int>
// int val1 = (s[i] % M1 + M1) % M1 + 1;
// int val2 = (s[i] % M2 + M2) % M2 + 1;
rh1[i + 1] = (rh1[i] * P1 + val1) % M1;
rh2[i + 1] = (rh2[i] * P2 + val2) % M2;
}
}
// --- 5. Core: Get Substring Hash ---
// Returns hash of S[L...R] (inclusive, 0-based) in O(1)
pair<ll, ll> getHash(int L, int R) {
if (L > R)
return {0, 0};
int len = R - L + 1;
// H(L...R) = h[R+1] - h[L] * P^len
ll hash1 = (h1[R + 1] - (h1[L] * pow1[len]) % M1 + M1) % M1;
ll hash2 = (h2[R + 1] - (h2[L] * pow2[len]) % M2 + M2) % M2;
return {hash1, hash2};
}
// --- 6. Core: Get Reverse Substring Hash ---
// Returns hash of reversed S[L...R] in O(1)
pair<ll, ll> getReverseHash(int L, int R) {
if (L > R)
return {0, 0};
int len = R - L + 1;
int revL = n - 1 - R;
int revR = n - 1 - L;
ll hash1 = (rh1[revR + 1] - (rh1[revL] * pow1[len]) % M1 + M1) % M1;
ll hash2 = (rh2[revR + 1] - (rh2[revL] * pow2[len]) % M2 + M2) % M2;
return {hash1, hash2};
}
// --- 7. Utility: Palindrome Check O(1) ---
bool isPalindrome(int L, int R) {
return getHash(L, R) == getReverseHash(L, R);
}
};
// --- Static Initialization ---
// Must be outside the struct
vector<ll> PolyHash::pow1{1};
vector<ll> PolyHash::pow2{1};
// 0 1 2 3 4
// 0 1 2 3 4 5
void shihab(){
string s;cin >> s;
PolyHash S(s);
int n = s.size();
int ans = 0;
int last = 0;
for(int i=0;i<n/2;i++){
if(S.getHash(last, i) == S.getHash(n-1-i, n-1-last)){
last = i+1;
ans += 2;
if(i == n-i-1 && (!(n&1)))ans--;
}
// dbg(i,last,ans);
}
ans++;
cout << ans << endl;
}
int32_t main(){
fast_io;
int tc;cin >> tc;
int test_case = 1;
while(tc--){
// cout<<"Case "<< test_case++ <<": ";
shihab();
}
return 0;
}
