Shortest Repeating Substring Length

You are given a non-empty string s consisting of lowercase letters. Your task is to determine the length of the shortest substring which, when repeated some number of times, produces s exactly.

More formally, find the smallest integer l such that there exists a string t of length l with s = t repeated k times for some positive integer k. If no such smaller substring exists, then l equals the length of s.

This problem may include some underlying number theory and string processing techniques that are commonly used in coding competitions. The answer should be computed using efficient iteration through possible divisors of the length of s.

Note: All formulas must be written in LaTeX format. For example, the condition can be stated as: find the smallest l such that \( s = t^k \), where \( t \) is a substring of length \( l \) and \( k = \frac{|s|}{l} \).

inputFormat

The input is given via standard input and has the following format:

T
s₁
s₂
…
s_T

Where:

• T is an integer representing the number of test cases.
• Each sᵢ is a non-empty string consisting of lowercase letters.

outputFormat

For each test case, output a single line with an integer representing the length of the shortest substring that can be repeated to form the given string.

## sample

6
abab
abcdef
aaa
abcabcabc
aabb
abababab

2
6
1
3
4
2

</p>