## FINDSR - Find String Roots

no tags

In mathematics, the N-th root of a number M, is a number K such that KN = M , i.e. KKK ... K = M where K is multiplied N times.

We can translate this into strings. In string notation, the juxtaposition is concatenation instead of multiplication. So, the N-th root of a string S is another string T such that TN = S, where T N = TTT ... T is the string T concatenated N times. For instance, if S = “abcabcabcabc”, for N = 2 the string T = “abcabc” is the N-th root of S, while for N = 4 its N-th root is T = “abc”. Note that for N = 1 any string S is the N-th root of S itself.

Given a string S you have to find the maximum N such that the N-th root of S exists. In the above example the answer would be 4, because there is no N-th root of S = “abcabcabcabc” for N > 4.

### Input

The input contains several test cases, each one described in a single line. The line contains a non-empty string S of at most 105 characters, entirely formed of digits and lowercase letters. The last line of the input contains a single asterisk (“*”) and should not be processed as a test case.

### Output

For each test case output a single line with the greatest integer N such that there exists a string T that concatenated N times is equal to S.

### Example

```Input:
abcabcabcabc
abcdefgh012
aaaaaaaaaa
*

Output:
4
1
10```

hide comments
 < Previous 1 2 3 4 5 Next > Vaibhav : 2010-09-01 00:28:05 I actually do it without any major string algorithms. But a little slower than other ACs

 Added by: Pablo Ariel Heiber Date: 2010-08-22 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC PERL6 VB.NET Resource: FCEyN UBA ICPC Selection 2009