RT

#include <bits/stdc++.h>

using namespace std;
int n, ans, pos, r, tt;
int p[22000020];
char s[22000020], t[22000020];
int main() {
	scanf("%d", &tt);
	while (tt--) {
		memset(p, 0, sizeof(p));
		ans = -1; n = 0; pos = 0; r = 0;
		scanf("%s", s+1);
		n = strlen(s+1);
		
		for (int i = 1, j = 0; i <= n; ++i) {
			t[++j] = '*';
			t[++j] = s[i];
		}
	
		t[2*n+1]='*';
		t[0]= '*';
		n = n * 2 + 1;
		
		for (int i = 1; i <= n; i ++) {
			if (i > r) {
				p[i] = 0;
			}
			else {
				p[i] = min(r-i, p[pos*2-1]);
			}

			while (t[i-p[i]-1] == t[i+p[i]+1]) {
				++p[i];
			}
	
			if (i + p[i] > r) {
				r = i + p[i];
				pos = i;
			}
			ans = max(ans, p[i]);
		}
		
		printf("%d\n", ans);
	}
	return 0;
}