#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int b1=131;
const int b2=13131;

char s[1000005];
int h1[1000005],h2[1000005];
int p1[1000005],p2[1000005];
signed main(){
	p1[0]=p2[0]=1;
	for(int i=1;i<=1000000;i++){
		p1[i]=p1[i-1]*b1;
		p2[i]=p2[i-1]*b2;
	}
	
	while(1){
		cin>>s;
		if(s[0]=='.'){
			break;
		}
		int n=strlen(s);
		
		h1[0]=h2[0]=0;
		for(int i=0;i<n;i++){
			int now=s[i];
			h1[i+1]=h1[i]*b1+now;
			h2[i+1]=h2[i]*b2+now;
		}
		
		for(int i=1;i<=n;i++){
			if(n%i!=0){
				continue;
			}
			bool f=1;
			for(int j=i;j<n;j+=i){
				if(h1[i]!=(h1[j+i]-h1[j]*p1[i]) || h2[i]!=(h2[j+i]-h2[j]*p2[i])){
					f=0;
					break;
				}
			}
			if(f){
				cout<<n/i<<'\n';
				break;
			}
		}
	}
} 

https://xwjedu.cn/p/T1455

#include<bits/stdc++.h>
using namespace std;

const int N =1e6+10;
typedef unsigned long long ull;

char s1[N],s2[N];
ull power[N],sum[N];
const ull b=131;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    power[0]=1;
    for(int i=1;i<N;i++){
        power[i]=power[i-1]*b;
    }

    int t;
    scanf("%d", &t);
    while (t--){
        scanf("%s %s",s1+1,s2+1);
        int n=strlen(s1+1);
        int m=strlen(s2+1);

        sum[0]=0;
        for(int i=1;i<=m;i++){
            sum[i]=sum[i-1]*b+(s2[i]-'A'+1);
        }
        ull hash_s1=0;
        for(int i=1;i<=n;i++){
            hash_s1=hash_s1*b+(s1[i]-'A'+1);
        }
        int ans=0;
        for(int i=0;i<=m-n;i++){
            ull sub_hash=sum[i+n]-sum[i]*power[n];
            if(sub_hash==hash_s1){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}