using namespace std;
#include <cstdio>
#define Lmax 1000011

int p[Lmax];
char s[Lmax + 1];

int solve();

int main()
{
	int t;
	freopen("prefix.in", "r", stdin);
	freopen("prefix.out", "w", stdout);

	for (scanf("%d\n", &t); t; --t)
	{
		scanf("%s\n", s + 1);

		printf("%d\n", solve());
	}

    return 0;
}

int solve()
{
	int i, k, res;

	for (res = 0, k = 0, i = 2; s[i]; ++i)
	{
		while (k > 0 && s[k + 1] != s[i]) k = p[k];
		if (s[k + 1] == s[i]) ++k;

		p[i] = k;

		if (k && k % (i - k) == 0) res = i;
	}

	return res;
}