/**
* Notes during contest.
*
* ------ A ------
* In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
* that the subset of pillars shall be connected in order?
*
* ------ B ------
* [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
* can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
* problems...
*
* ------ C ------
*
* Time Complexity 1: O()
* Time Complexity 2: O(n^2)
* Time Complexity 3: O()
* Implementation 1
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
inline vec z_array(const std::string& s) {
int_t n = s.size();
vec z(n, 0);
for (int_t k = 1, x = 0, y = 1; k < n; k++) {
z[k] = std::max(std::min(z[k - x], y - k + 1), int_t(0));
while (k + z[k] < n && s[k + z[k]] == s[z[k]])
x = k, y = k + z[k], z[k]++;
}
// std::cerr << "[debug] " << s << std::endl;
// for (int_t a : z)
// std::cerr << a << ' ';
// std::cerr << std::endl;
return z;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int_t T;
std::cin >> T;
for (int_t tc = 1; tc <= T; tc++) {
std::string str;
std::cin >> str;
int_t n = str.length();
if (n > 10000) {
std::cout << "bye\n";
return 0;
}
vec dp(n, 1);
for (int_t k = (n - 1) / 2; k >= 0; k--) {
std::string substr = str.substr(k, n - 2 * k);
vec Z = z_array(substr);
for (int_t i = n - 2 * k - 1; i > 0; i--) {
assert(Z[i] <= n - 2 * k - i);
if (Z[i] != n - 2 * k - i || 2 * Z[i] > n - 2 * k)
continue;
if (2 * Z[i] == n - 2 * k) { // even palindrome
dp[k] = std::max(dp[k], int_t(2));
} else { // odd palindrome
dp[k] = std::max(dp[k], dp[k + Z[i]] + 2);
}
}
}
std::cout << dp[0] << '\n';
}
}
