Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Each test case is a line of input representing s, a string of printable characters.

For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

#include 
     
      #include 
      
       using namespace std;int next[1000002];string str;int len;void get_next(string T, int next[]){    int i,j;    next[1]=0;    j=0;i=1;    while(i
       
        >str && str!="."){        len=str.length();        get_next(str, next);        if(len%(len-next[len])==0)            cout<