#include <bits/stdc++.h>
#define X 145443351LL
#define mod 1000000007LL
using namespace std;
typedef long long ll;
ll Hash[1000010], n, pot[1000010];
inline bool compare(int i, int j, int ii, int jj)
{
ll dx = (i > 0 ? Hash[i - 1] : 0);
ll A = (mod + Hash[j] - dx)%mod;
ll dx2 = (ii > 0 ? Hash[ii - 1] : 0);
ll A2 = (mod + Hash[jj] - dx2)%mod;
return (((A*pot[ii])%mod) == ((A2*pot[i])%mod));
}
string s;
int solve(int ini)
{
int fim = s.size() - 1 - ini;
if(ini == fim) return 1;
if(ini > fim) return 0;
int best = 1;
for(int p = ini; p <= (ini + fim)/2; p++)
{
if(compare(ini, p, fim - p + ini, fim))
{
best = max(best, 2 + solve(p + 1));
break;
}
}
return best;
}
int T;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>T;
pot[0] = 1;
for(int i = 1; i < 1000010; i++) pot[i] = (pot[i - 1]*X)%mod;
while(T--)
{
cin>>s;
n = s.size();
Hash[0] = 0;
for(int i = 0; i < n; i++)
{
if(i > 0) Hash[i] = Hash[i - 1];
Hash[i] = (Hash[i] + s[i]*pot[i])%mod;
}
cout<<solve(0)<<"\n";
}
}
