Smallest Repeating Unit in DNA Sequences

Given a DNA sequence, the task is to determine the length of the smallest repeating unit that, when repeated several times, forms the entire sequence.

More formally, for a given string \( s \) of length \( n \), find the smallest integer \( k \) (with \( 1 \le k \le n \)) such that \[ s = \underbrace{s[0:k] \ s[0:k] \ \cdots \ s[0:k]}_{\text{repeated }\frac{n}{k}\text{ times}}, \] where the notation \( s[0:k] \) represents the prefix of \( s \) with length \( k \). If no such \( k \) exists (which happens when the sequence does not have any proper repeating pattern), then \( k \) equals \( n \) itself.

You are provided multiple test cases. For each test case, output the length of the smallest repeating unit.

inputFormat

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

T
s1
s2
...
sT

Where:

• T is an integer representing the number of test cases.
• Each of the following T lines contains a DNA sequence string s.

outputFormat

For each test case, print a single integer on a new line representing the length of the smallest repeating unit of the corresponding DNA sequence.

## sample

3
ACACAC
AGTAAGTA
GATTACA

2
4
7

</p>