Minimum Repeating Segment Length

You are given one or more mosaic patterns. Each pattern is represented as a string consisting of uppercase letters. The goal is to determine the minimum length of a segment (substring) such that repeating this segment some number of times produces the entire pattern. In other words, for a given string S with length n, you need to find the smallest integer k (where k divides n) for which

\(S = (S[0:k])^{n/k}\)

For example, if S is "ABABAB", the answer is 2 because "AB" repeated 3 times gives "ABABAB".

The input is provided via standard input. The first line contains an integer T denoting the number of test cases. Each of the following T lines contains a mosaic pattern. For each test case, output the minimum repeating segment length on a separate line.

inputFormat

The input is read from stdin and has the following format:

T
pattern1
pattern2
... 
patternT

Where:

• T is an integer representing the number of test cases.
• Each pattern is a non-empty string composed of uppercase letters.

outputFormat

For each test case, output a single integer representing the minimum length of the segment that can be repeated to form the given mosaic pattern. Each result should be printed on a new line on stdout.

## sample

4
ABABAB
AAAA
ABCABC
A

2
1
3
1

</p>