Будемо казати, що символьний рядок має період k, якщо він може бути утворений шляхом об'єднання одного чи декількох однакових рядків довжиною k. Наприклад, рядок "abcabcabcabc" має період 3, так як він може бути утворений шляхом об'єднання 4-х рядків "abc". Він також має період 6 (об'єднанння двох рядків "abcabc") та 12 (сам рядок "abcabcabcabc").
Напишіть програму, яка визначає найменший період заданого рядка.
У першому рядку задано кількість тестових випадків N у вхідних даних. Кожен тестовий випадок розміщено у окремому рядку і містить не більше 80 символів без пропусків.
Вивести для кожного тестового випадку шукане значення найменшого періода рядка. Різні тестові випадки повинні бути відокремлені порожнім рядком.