#include<bits/stdc++.h>
using namespace std;
using i64=long long;
int n;
char str[100010];
namespace ds1{
int nex[200010][26],len[200010],lnk[200010],tot=1,lst=1;
int extend(int c){
   int u=++tot,p=lst;
   len[u]=len[p]+1;
   for(;p&&!nex[p][c];p=lnk[p])nex[p][c]=u;
   if(!p)lnk[u]=1;
   else{
      int q=nex[p][c];
      if(len[p]+1==len[q])lnk[u]=q;
      else{
         int v=++tot;
         copy_n(nex[q],26,nex[v]),lnk[v]=lnk[q],len[v]=len[p]+1;
         for(;p&&nex[p][c]==q;p=lnk[p])nex[p][c]=v;
         lnk[q]=lnk[u]=v;
      }
   }
   return lst=u;
}
vector<int>G[2000010];
int dfn[2000010],fa[2000010],id[100010],mi[21][2000010],dtot;
inline bool cmp(int x,int y){
   return dfn[x]<dfn[y];
}
void dfs(int u){
   dfn[u]=++dtot,mi[0][dfn[u]]=fa[u];
   for(int v:G[u])dfs(v);
}
inline int lca(int l,int r){
   if(l==r)return l;
   l=dfn[l],r=dfn[r];
   if(l>r)swap(l,r);
   l++;int g=__lg(r-l+1);
   return min(mi[g][l],mi[g][r-(1<<g)+1],cmp);
}
void init(){
   for(int i=1;i<=n;i++)id[i]=extend(str[i]-'a');
   for(int i=2;i<=tot;i++){
      fa[i]=lnk[i],G[fa[i]].push_back(i);
   }
   dfs(1);
   for(int i=1;i<=20;i++)for(int k=1;k+(1<<i)-1<=tot;k++)
   mi[i][k]=min(mi[i-1][k],mi[i-1][k+(1<<i-1)],cmp);
}
}
namespace ds2{
constexpr int B=350;
int s1[100010],s2[B];
inline void add(int l,int r,int w){
   s1[l]+=w,s2[l/B]+=w,s1[r+1]-=w,s2[(r+1)/B]-=w;
}
inline int ask(int p){
   int s=0;
   for(int i=p;i>=0&&i/B==p/B;i--)s+=s1[i];
   for(int i=p/B-1;i>=0;i--)s+=s2[i];
   return s;
}
}
i64 ans;
vector<int>num[1000010];
int nex[1000010],pre[1000010],mip[1000010],p[1000010],pn,del[200010];
void dfs(int i,int S){
   for(int u:num[S])ans+=ds2::ask(u)*(u+1ll);
   for(int k=i+1;k<=pn&&S*p[k]<n;k++){
      vector<int>recov;
      for(int w=p[k];w<=n;w+=p[k])if(!del[w]){
         int x=pre[w],y=nex[w],u=1;
         if(x>=1)u=max(u,ds1::lca(ds1::id[x],ds1::id[w]),ds1::cmp);
         if(y<=n)u=max(u,ds1::lca(ds1::id[y],ds1::id[w]),ds1::cmp);
         del[w]=u,recov.push_back(w);
         ds2::add(ds1::len[u],ds1::len[ds1::id[w]]-1,-1);
         nex[x]=y,pre[y]=x;
      }
      dfs(k,S*p[k]);
      reverse(begin(recov),end(recov));
      for(int w:recov){
         int x=pre[w],y=nex[w];
         ds2::add(ds1::len[del[w]],ds1::len[ds1::id[w]]-1,1);
         nex[x]=w,pre[y]=w,del[w]=0;
      }
   }
}
int main(){
   scanf("%d%s",&n,str+1);
   for(int i=2;i<n;i++){
      if(!p[i])p[++pn]=i,mip[i]=i;
      for(int k=1;k<=pn&&i*p[k]<=n;k++){
         p[i*p[k]]=1,mip[i*p[k]]=p[k];
         if(i%p[k]==0)break;
      }
   }
   for(int i=1;i<n;i++){
      int x=i,y=1;
      for(;x>1;){
         int w=mip[x];y*=w;
         for(;x%w==0;x/=w);
      }num[y].push_back(i);
   }
   ds1::init();
   for(int i=2;i<=ds1::tot;i++)ds2::add(ds1::len[ds1::lnk[i]],ds1::len[i]-1,1);
   vector<int>perm;
   for(int i=1;i<=n;i++)perm.push_back(i);
   sort(begin(perm),end(perm),[](int x,int y){
      return ds1::cmp(ds1::id[x],ds1::id[y]);
   });
   perm.insert(begin(perm),0),perm.push_back(n+1);
   for(int i=1;i<=n+1;i++){
      nex[perm[i-1]]=perm[i];
      pre[perm[i]]=perm[i-1];
   }dfs(0,1);
   cout<<ans+1;
   return 0;
}