1 #include<cstdio>

  2 #include<algorithm>

  4 #include<iostream>

  5 #include<cmath>

  6 #include<cstring>

  7 using namespace std;

  8

  9 #define F(x) ((x)/3+((x)%3==1?0:tb))

 10 #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

 11

 12

 13 //sa:字典序中排第i位的起始位置在s中第sa[i]

 14

 15 //rnk:就是s第i个位置的后缀是在字典序排第几

 16

 17 //height：字典序排i和i-1的后缀的最长公共前缀

 18

 19 const int MAXN = 3e6+10;//n*10

 20 int sa[MAXN];

 21 int rnk[MAXN];

 22 int height[MAXN];

 23 int n;

 24 char s[MAXN];

 25 int r[MAXN];

 26 int wa[MAXN],wb[MAXN],wv[MAXN];

 27 int wws[MAXN];

 28

 29 void sort(int *r,int *a,int *b,int n,int m)

 30 {

 31       int i;

 32       for(i=0;i<n;i++) wv[i]=r[a[i]];

 33       for(i=0;i<m;i++) wws[i]=0;

 34       for(i=0;i<n;i++) wws[wv[i]]++;

 35       for(i=1;i<m;i++) wws[i]+=wws[i-1];

 36       for(i=n-1;i>=0;i--) b[--wws[wv[i]]]=a[i];

 37      return;

 38 }

 39

 40 int c0(int *r,int a,int b)

 41 {

 42     return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];

 43 }

 44

 45 int c12(int k,int *r,int a,int b)

 46 {

 47     if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);

 48     else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];

 49 }

 50

 51 void dc3(int *r,int *sa,int n,int m)

 52 {

 53     int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;

 54     r[n]=r[n+1]=0;

 55     for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;

 56     sort(r+2,wa,wb,tbc,m);

 57     sort(r+1,wb,wa,tbc,m);

 58     sort(r,wa,wb,tbc,m);

 59     for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)

 60           rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;

 61     if(p<tbc) dc3(rn,san,tbc,p);

 62           else for(i=0;i<tbc;i++) san[rn[i]]=i;

 63     for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;

 64     if(n%3==1) wb[ta++]=n-1;

 65     sort(r,wb,wa,ta,m);

 66     for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;

 67     for(i=0,j=0,p=0;i<ta && j<tbc;p++)

 68           sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];

 69     for(;i<ta;p++) sa[p]=wa[i++];

 70     for(;j<tbc;p++) sa[p]=wb[j++];

 71     return;

 72 }

 73

 74 void calheight(int *r, int *sa, int n)

 75 {

 76     // 此处n为实际长度

 77     int i, j, k = 0;

 78      // height[]的合法范围为 1~n, 其中0是结尾加入的字符

 79     for (i = 1; i <= n; ++i) rnk[sa[i]] = i;

 80      // 根据SA求RANK

 81     for (i = 0; i < n; height[rnk[i++]] = k)

 82     // 定义：h[i] = height[ RANK[i] ]

 83         for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; ++k);

 84     //根据 h[i] >= h[i-1]-1 来优化计算height过程

 85     return;

 86 }

 87

 88 int main()

 89 {

 90     ios::sync_with_stdio(false);

 91     cin.tie(0);

 92     cout.tie(0);

 93     while(cin>>s){

 94         if(s[0]=='.') break;

 95         int len=strlen(s);

 96         for(int i=0;i<len;i++)

 97             r[i]=s[i]-'a'+1;

 98         r[len]=0;

 99         dc3(r,sa,len+1,105);

100         calheight(r,sa,len);

101         int flag=0;

102         for(int i=1;i<=len;i++){

103             if(len%i==0&&rnk[0]==rnk[i]+1&&height[rnk[0]]==len-i){

104                 cout<<len/i<<endl;

105                 flag=1;

106                 break;

107             }

108         }

109         if(!flag) cout<<1<<endl;

110     }

111     return 0;

112 }