#define DM 1000002
#define mem(x, y) for(int i=0;i<y;++i)x[i]=0
#include <fstream>
using namespace std;

ifstream fi ("prefix.in");
ofstream fo ("prefix.out");
char s[DM];
int t, n, bst, p[DM];

int strlen(char s[]) {
	int rez = 1;
	while (s[rez+1] != '\0')
		++rez;
	return rez;
}

void calcprefix() {
	int k = 0;
	for (int i = 2; i <= n; ++i) {
		while (k && s[i] != s[k+1])
			k = p[k];
		if (s[k] == s[i+1])
			++k;
		p[i] = k;
	}
}

int analyze() {
	int lg = 1, k = 0, rez = 0;
	for (int i = 2; i <= n; ++i) {
		while (k && s[i] != s[k+1]) {
			k = p[k];
			lg = i - 1 - k;
		}
		if (s[i] == s[k+1]) {
			++k;
			if (k == lg) {
				rez = i;
				k = 0;
			}
		} else {
			lg = i;
			k = 0;
		}
	}
	return rez;
}

int main() {
	fi >> t;
	while (t--) {
		fi >> s + 1;
		n = strlen(s);
		calcprefix();
		fo << analyze() << '\n';
		mem(p, DM);
	}
	return 0;
}