#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=1e5+10,M=N*2,V=26;
int n;
int cnt,pri[N],vis[N],mu[N];
vector<int>d[N],to[M];
void init(){
	for(int i=2;i<=n;i++){
		if(!vis[i])pri[++cnt]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=pri[i];j<=n;j+=pri[i])d[j].push_back(i);
	}
}
char a[N];
int k=1,las=1,fail[M],ch[M][V],len[M],cur[M],val[M];
void append(int c){
	int now=++k,x=las;
	len[now]=len[las]+1;
	for(;x&&!ch[x][c];x=fail[x])ch[x][c]=now;
	if(x){
		int y=ch[x][c];
		if(len[y]!=len[x]+1){
			int ne=++k;
			copy(ch[y],ch[y]+V,ch[ne]);
			len[ne]=len[x]+1,fail[ne]=fail[y],fail[y]=fail[now]=ne;
			for(;x&&ch[x][c]==y;x=fail[x])ch[x][c]=ne;
		}else fail[now]=y;
	}else fail[now]=1;
	las=now;
}
const int B=21;
int f[1<<B],g[1<<B];
ll ans=0;
int st,ed;
void calc(int S,int l,int r){
	l-=st,r-=st;
	r>B&&(r=B),l<0&&(l=0);
	if(l>=r)return;
	S=(S&(1<<r)-1)>>l<<l;
	ans+=f[S]+g[S]*(st+1);
}
int dft,dfn[M],fa[M],Len[M];
void make(int u){
	Len[dfn[u]=++dft]=len[u];
	for(int v:to[u])make(v),fa[dfn[v]]=dfn[u];
}
ull his[N],s[N];
ull U;
void solve0(int i){
	U=0;
	fill(s,s+1+cnt,0);
	int lim=min(n-i+1,B*3);
	U=(1ull<<lim)-1;
	for(int p=30;p<=cnt;p++){
		int w=(pri[p]-i%pri[p])%pri[p];
		if(w<lim)s[p]|=1ull<<w;
	}
	for(int j=0;i+j<=n&&j<B*3;j++){
		for(int p=1;p<=cnt&&p<30;p++){
			if((i+j)%pri[p]==0)s[p]|=1ull<<j;
		}
	}
}
void solve1(int i){
	solve0(i);
	// debug(ary(s,1,cnt));
	fill(his,his+1+n,U);
	for(int j=1;j<=n;j++){
		for(int x:d[j])his[j]&=~s[x];
	}
}
void solve2(int i){
	memset(val,0,sizeof val);
	for(int j=1;j<=n;j++){
		val[cur[j]]=his[j]&(1ull<<B)-1;
	}
	st=i;
	for(int i=k;i>=2;i--){
		val[fa[i]]|=val[i];
		calc(val[i],Len[fa[i]],Len[i]);
	}
	fill(val,val+1+k,0);
	for(int j=1;j<=n;j++){
		val[cur[j]]=his[j]>>B&(1ull<<B)-1;
	}
	st=i+B;
	for(int i=k;i>=2;i--){
		val[fa[i]]|=val[i];
		calc(val[i],Len[fa[i]],Len[i]);
	}
	fill(val,val+1+k,0);
	for(int j=1;j<=n;j++){
		val[cur[j]]=his[j]>>B+B&(1ull<<B)-1;
	}
	st=i+B+B;
	for(int i=k;i>=2;i--){
		val[fa[i]]|=val[i];
		calc(val[i],Len[fa[i]],Len[i]);
	}
}
int main(){
	scanf("%d%s",&n,a+1);
	for(int S=1;S<(1<<B);S++){
		int i=__builtin_ctz(S);
		f[S]=f[S^1<<i]+i,g[S]=g[S^1<<i]+1;
	}
	init();
	for(int i=n;i>=1;i--)append(a[i]-'a'),cur[i]=las;
	for(int i=2;i<=k;i++)to[fail[i]].push_back(i);
	make(1);
	for(int i=1;i<=n;i++)cur[i]=dfn[cur[i]];
	for(int i=0;i<n;i+=B*3){
		solve1(i);
		solve2(i);
	}
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif