#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1'000'000 + 10;
const int MAX_LG = 21;
int n;
string s;
namespace Hash {
const int M = 998'244'353;
inline int Sum(int a, int b) {
a += b;
if (a >= M) a -= M;
else if (a < 0) a += M;
return a;
}
inline int Mul(int a, int b) { return 1LL * a * b % M; }
const int B = 9973;
int pw[MAX_N], hash[MAX_N];
inline void preprocess() {
pw[0] = 1;
for (int i = 1; i < MAX_N; ++i) {
pw[i] = Mul(pw[i - 1], B);
}
}
inline void build() {
for (int i = 1; i <= n; ++i) {
hash[i] = Sum(Mul(B, hash[i - 1]), s[i - 1]);
}
}
inline int get_hash(int l, int r) {
return Sum(hash[r + 1], -Mul(hash[l], pw[r - l + 1]));
}
inline int lcs(int x, int y) {
int l = 0, r = min(x, y) + 2, mid;
while (r - l > 1) {
mid = (l + r) >> 1;
if (get_hash(x - mid + 1, x) == get_hash(y - mid + 1, y))
l = mid;
else
r = mid;
}
return l;
}
void reset() {
fill_n(hash + 1, n, 0);
}
}
int calc(int l, int r) {
if (l >= r) return 0;
for (int i = l; i < r - 1; ++i) {
if (Hash::lcs(i, r - 1) > i - l) {
return 2 + calc(i + 1, r - (i - l + 1));
}
}
return 1;
}
void solve_test() {
cin >> s;
n = int(s.size());
Hash::build();
cout << calc(0, n) << '\n';
}
void clear_vars() {
Hash::reset();
n = 0;
s.clear();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
Hash::preprocess();
int T;
cin >> T;
while (T--) {
solve_test();
clear_vars();
}
}
