#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000000

char s[MAX_LEN + 2]; // terminat cu '\n\0'
int Z[MAX_LEN];

inline int MIN(int X, int Y) {
	return X < Y ? X : Y;
}

int main(void) {
	int numTests, n;
	int l, r;
	int q;
	FILE *fin = fopen("prefix.in", "r");
	FILE *fout = fopen("prefix.out", "w");

	fscanf(fin, "%d\n", &numTests);
	while (numTests--) {
		fgets(s, MAX_LEN + 1, fin);
		n = strlen(s) - 1;
		l = r = 0;
		q = 0;
		for (int i = 1; i < n; i++) {
			Z[i] = (MIN(r - i + 1, Z[i - l]) & -(i <= r));
			while (s[Z[i]] == s[i + Z[i]]) {
				Z[i]++;
			}
			if (i + Z[i] - 1 > r) {
				r = i + Z[i] - 1;
				l = i;
			}
			if (Z[i] / i * i > q) {
				q = Z[i] / i * i + i;
			}
		}
		fprintf(fout, "%d\n", q);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}