FINDSR  Find String Roots
In mathematics, the Nth root of a number M, is a number K such that K^{N} = 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 Nth root of a string S is another string T such that T^{N} = 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 Nth root of S, while for N = 4 its Nth root is T = “abc”. Note that for N = 1 any string S is the Nth root of S itself.
Given a string S you have to find the maximum N such that the Nth root of S exists. In the above example the answer would be 4, because there is no Nth 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 nonempty string S of at most 10^{5} 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
Anmol Pandey:
20150128 14:15:09
Superb Question .


Deepak Gupta:
20140911 13:50:20
Was getting TLE when using memset for each case.Got AC by removing it 

Superty:
20140821 17:07:38
Ad hoc problem. 

___Durgesh___:
20140719 10:03:38
interesting one :) 

Mitch Schwartz:
20131024 15:34:16
@prudhvi: I havent experimented to find max number of test cases in an input file, but surely you can see that using only strings of random letters will tend to miss all the interesting cases for this problem? 

prudhvi:
20131024 15:01:58
HOW MANY TEST CASES ARE THERE?


Mitch Schwartz:
20130912 04:12:18
@Gupta: You have expressed the notion that "getting correct answers for the sample input is a good indicator that my solution is correct". In general, the sample input/output may be quite simple, designed more for basic understanding of the problem and expected formatting rather than helping users uncover common bugs. Many people express this notion in comments, and I don't know why they do; it's completely unfounded and just takes up space. Moreover, giving additional cases in the comments is very often a spoiler, yet it is common all the same. You may try the forum for help with debugging. 

Gupta:
20130911 16:28:03
Is there any special test case for this problem?I am getting the correct answer for the above mentioned test cases but while submitting I am getting WA.Plz comment


abdou_93:
20130628 12:17:58
nice

Added by:  Pablo Ariel Heiber 
Date:  20100822 
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 