#include <fstream>
#include <cstring>
#define DIM 1000005

using namespace std;

ifstream f("prefix.in");
ofstream g("prefix.out");

char S[DIM];

int Pi[DIM];

int T;

int main() {
	f >> T;
	f.get();
	f.get(S, DIM, EOF);
	int p = 0;
	while (T--) {
		//f >> S + 1;
		Pi[1] = 0;
		int pp = p;
		++p;
		for (int i = 2; S[p] != 0 && S[p] != '\n'; ++i, ++p) {
			int q = Pi[i - 1];
			while (q && S[p] != S[pp + q])
				q = Pi[q];
			if (S[p] == S[pp + q])
				Pi[i] = q + 1;
			else
				Pi[i] = 0;
		}
		int sol = 0;
		p = pp;
		for (int i = 1; S[p] != 0 && S[p] != '\n'; ++i, ++p)
		if (Pi[i] != 0 && i % (i - Pi[i]) == 0)
			sol = i;
		++p;
		g << sol << "\n";
	}
	return 0;
}