Compute Repetition Count of a Periodic String

Given a non-empty string S consisting of lowercase English letters, a periodic substring p is defined as the shortest substring such that S can be constructed by concatenating one or more copies of p. In each operation, you remove one occurrence of p from S. Your task is to find the minimum number of operations required to completely remove S, which is equivalent to finding the number of times p is repeated in S.

Formally, if S can be expressed as \(p^k\) where \(p\) is the smallest period of S, then the answer is \(k=\frac{|S|}{|p|}\), where \(|S|\) denotes the length of S and \(|p|\) is the length of the period.

inputFormat

The first line contains an integer T denoting the number of test cases. Each of the following T lines contains a non-empty string S made up of lowercase English letters.

outputFormat

For each test case, output an integer on a new line representing the number of repetitions (or operations) required to remove the string, i.e. \(\frac{|S|}{|p|}\).

5
abababab
aaaa
ababa
abcabcabc
abcd

4
4
1
3
1