Shortest Repeating Unit

You are given a string s composed of lowercase letters. Your task is to determine the length of the shortest substring u such that s can be formed by concatenating one or more copies of u.

Formally, find the smallest integer L such that there exists a substring \( u = s[0:L] \) where \[ s = \underbrace{u + u + \cdots + u}_{k \text{ times}}, \quad k \ge 1 \] If no such shorter substring exists, the answer is \(|s|\).

Example:

• For s = "ababab", the answer is 2 since "ab" repeated 3 times forms "ababab".
• For s = "abcabcabc", the answer is 3 because "abc" repeated 3 times forms "abcabcabc".
• For s = "aaaa", the answer is 1.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains a string s.

Input format:

T
s1
s2
...
sT

outputFormat

For each test case, output a single integer — the length of the shortest substring u that can be repeated to form the given string s.

Output format: Each answer is printed on a new line.

## sample

3
ababab
abcabcabc
aaaa

2
3
1

</p>