Периодические строки

Будем говорить, что символьная строка имеет период k, если она может быть образована путем объединения одной или нескольких одинаковых строк длиной k. Например, строка "abcabcabcabc" имеет период 3, так как она может быть образована путём объединения 4-х строк "abc". Она также имеет период 6 (объединение двух строк "abcabc") и 12 (сама строка "abcabcabcabc").

Напишите программу определяющую наименьший период заданной строки.

Технические условия

Входные данные

В первой строке задано количество тестовых случаев N во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более 80 символов без пробелов.

Выходные данные

Вывести для каждого тестового случая искомое значение наименьшего периода строки. Разные тестовые случаи должны быть разделены пустой строкой.

Информация о задаче

Лимит времени: 3 секунды
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 17% 73/88
Классификация: Алгоритмы на строках

Пример

Пример входных данных

2
HoHoHo
mama

Пример выходных данных

2

2

← ЖК-дисплей