String Exponentiation

Time limit1sMemory limit256 MB

Summary

Given a string, find the largest exponent n such that the string is a repetition of some base string a raised to n.

Level: Medium5 of 10
Topics: String, String matching, Number theory
Solved: No attempts yet

Problem

For two strings $a$ and $b$ made of lowercase letters, $a * b$ denotes their concatenation. For example, if $a=\texttt{abc}$ and $b=\texttt{def}$ , then $a * b=\texttt{abcdef}$ .

If we treat this concatenation as multiplication, we can also define exponentiation by a non-negative integer:

$a^0 = \varepsilon$ (the empty string)
$a^{n+1} = a * a^n$

Given a string $s$ , write a program that finds the largest $n$ for which some string $a$ satisfies $s = a^n$ .

Input

The input consists of at most 10 test cases. Each test case is a single line containing the string $s$ . The length of $s$ is at least 1 and at most 1,000,000. The line following the last test case contains a single period (.).

Output

For each test case, print on its own line the largest $n$ such that $s = a^n$ .

Examples6

Example 1
Input
```
abcd
aaaa
ababab
.
```
Expected output
```
1
4
3
```
Example 2
Input
```
a
.
```
Expected output
```
1
```
Example 3
Input
```
zzzzzzz
z
.
```
Expected output
```
7
1
```
Example 4
Input
```
abcabcab
abcabcabc
.
```
Expected output
```
1
3
```
Example 5
Input
```
abababababab
abab
.
```
Expected output
```
6
2
```
Example 6
Input
```
abababa
aabaab
.
```
Expected output
```
1
2
```