#include <bits/stdc++.h>
#include <cassert>
#define MAX_WORD_LENGTH 5100000
int longest_palindromic_partition(const std::string& word) {
const int n = word.length();
const unsigned int base = 131;
int done_chars = 0;
int n_chunks = 0;
while (done_chars * 2 < n) {
unsigned int left_hash = 0, right_hash = 0;
unsigned int base_power = 1;
for (int chunk_size = 1; true; chunk_size++) {
const int l = done_chars;
const int r = n - done_chars - chunk_size;
if (l + chunk_size - 1 >= r) {
return n_chunks + 1;
}
base_power = (chunk_size == 1) ? 1 : base_power * base;
left_hash += static_cast<unsigned int>(word[l + chunk_size - 1]) * base_power;
right_hash = static_cast<unsigned int>(word[r]) + right_hash * base;
if (left_hash == right_hash && word.compare(l, chunk_size, word, r, chunk_size) == 0) {
n_chunks += 2;
done_chars += chunk_size;
break;
}
}
}
return n_chunks;
}
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::string word;
std::cin >> word;
assert(word.length() <= MAX_WORD_LENGTH);
std::cout << longest_palindromic_partition(word) << std::endl;
}
return 0;
}
