#include <bits/stdc++.h>
using namespace std;
using ll=long long;using ull=unsigned long long;
const int N=2e5+10,A=(1<<16)-1;
int n;
ull Bt[1611],Bp[10011][1611],Bw[1611];
int pps[1<<16],ppc[1<<16],Bn;ll ans;
ll F(ull x,int i)
{
	i++;
	return pps[x>>48&A]+pps[x>>32&A]+pps[x>>16&A]+pps[x&A]+ppc[x>>48&A]*(48+i)+ppc[x>>32&A]*(32+i)+ppc[x>>16&A]*(16+i)+ppc[x&A]*i;
}
int len[N],fail[N],ed[N];
vector<int>G[N];
void cover(int l,int r)
{
	if(l&63)
	{
		ans+=F(Bt[l>>6]>>(l&63),l);
		Bt[l>>6]&=((ull)1<<(l&63))-1;
		l+=64-(l&63);
	}
	for(int i=l;i<=r;i+=64)
	{
		ans+=F(Bt[i>>6],i);
		Bt[i>>6]=0;
	}
}
vector<int>fp[N];
bool is[N];int pr[N];
void dfs(int u,int F)
{
	if(ed[u])
	{
		int n=len[u]-1,Bn=n>>6;
		for(int i=0;i<Bn;++i)Bw[i]=-1;
		if(!(n+1&63))Bw[n>>6]=-1;
		else Bw[n>>6]=((ull)1<<(n&63)+1)-1;
		for(int x:fp[ed[u]])for(int i=0;i<=Bn;++i)Bw[i]&=~Bp[x][i];
		for(int i=0;i<=Bn;++i)Bt[i]|=Bw[i];
	}
	for(int v:G[u])if(v^F)dfs(v,u);
	if(u)cover(len[fail[u]],len[u]-1);
}
int ch[N][26],sz,lst;
void g_SAM()
{
	string s;cin>>n>>s;fail[0]=-1;
	for(int z=1;z<=n;z++)
	{
		char c=s[z-1];int nw=++sz;len[nw]=len[lst]+1;ed[nw]=z;
		int p=lst;lst=nw;while(~p&&!ch[p][c-'a'])ch[p][c-'a']=nw,p=fail[p];
		if(!~p){fail[nw]=0;continue;}
		else
		{
			int q=ch[p][c-'a'];
			if(len[p]+1==len[q])fail[nw]=q;
			else
			{
				int cl=++sz;
				for(int i=0;i<26;++i)ch[cl][i]=ch[q][i];
				len[cl]=len[p]+1;fail[cl]=fail[q];fail[q]=fail[nw]=cl;
				while(~p&&ch[p][c-'a']==q)ch[p][c-'a']=cl,p=fail[p];
			}
		}
	}				
	for(int i=1;i<=sz;i++)G[fail[i]].push_back(i);
}
void sieve()
{
	is[0]=is[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!is[i])pr[++pr[0]]=i,fp[i].push_back(pr[0]);
		for(int j=1;j<=pr[0]&&i*pr[j]<=n;j++)
		{
			is[i*pr[j]]=1;fp[i*pr[j]]=fp[i];fp[i*pr[j]].push_back(j);
			if(i%pr[j]==0)break;
		}
	}
}
int main()
{
	g_SAM();sieve();
	for(int S=0;S<1<<16;S++)for(int i=0;i<16;i++)if(S>>i&1)ppc[S]++,pps[S]+=i;
	for(int i=1;i<=pr[0];i++)for(int j=0;j<=n;j+=pr[i])Bp[i][j>>6]|=(ull)1<<(j&63);
	Bn=n-1>>6;dfs(0,0);cout<<ans<<'\n';
}