#include <bits/stdc++.h>
using namespace std;
char c[21000005];
string s;
int n , len , p[21000005] , maxx , maxid , ans;
int main()
{
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
	{
	    cin >> s;
	    
	    len = s.length();
	    ans = 0; 
	    memset(p , 0 , sizeof(p));
	    c[0] = '@'; 
	    for (int j = 0 ; j <= len ; j++)
	    {
	        c[2 * j + 2] = s[j];
	        c[2 * j + 1] = '#';
	    }
	    
	    for (int j = 1 ; j <= 2 * len + 1 ; j++)
	    {
	    	p[i] = (maxx > j ? min(p[2 * maxid - j] , maxx - j) : 1);
	    	while (c[j - p[j]] == c[j + p[j]]) p[j]++;
			if (j + p[j] > maxx) {maxx = j + p[j]; maxid = j;}	
	        ans = max(ans , p[j] - 1);
		}
		cout << ans << endl;
	}
    return 0;
}