#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(function %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=2e5+5,B=1005;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n;char s[N];
struct Node{int s[26],fa,len;inline int&operator[](int x){return s[x];}}T[N<<1];
int tot=1,lst=1,pos[N];
void extend(int x){
  int cur=++tot;T[cur].len=T[lst].len+1;
  int p=lst;while(p&&!T[p][x]) T[p][x]=cur,p=T[p].fa;
  if(!p) T[cur].fa=1;
  else{
    int q=T[p][x];
    if(T[q].len==T[p].len+1) T[cur].fa=q;
    else{
      int clone=++tot;T[clone]=T[q];T[clone].len=T[p].len+1;
      while(T[p][x]==q) T[p][x]=clone,p=T[p].fa;
      T[q].fa=T[cur].fa=clone;
    }
  }lst=cur;
}
vector<int>G[N<<1];int dfn[N<<1],cdfn,st[18][N<<1];
int ord[N],pre[N],suf[N];
void dfs(int u,int fa){
  st[0][dfn[u]=++cdfn]=fa;
  for(int v within G[u]) dfs(v,u);
}int gmin(int x,int y){return dfn[x]<dfn[y]?x:y;}
int LCA(int x,int y){
  if(x==y) return x;
  if((x=dfn[x])>(y=dfn[y])) swap(x,y);
  int len=31^__builtin_clz(y-(x++));
  return gmin(st[len][x],st[len][y-(1<<len)+1]);
}
int pnt[N],blc[B],bel[N],siz;
void update(int L,int R,int C){
  if(L>R) return;
  pnt[L]+=C;pnt[R+1]-=C;blc[bel[L]]+=C;blc[bel[R+1]]-=C;}
int query(int x){
  int id=bel[x],s=0;
  For(i,1,id-1) s+=blc[i];
  For(i,(id-1)*siz+1,x) s+=pnt[i];
  return s;
}
int p[N],cp,lpf[N];bool vis[N];
vector<int>pt[N];
void init(int n){
  For(i,2,n){
    if(!vis[i]) p[++cp]=i,lpf[i]=i;
    For(j,1,cp){
      if(i*p[j]>n) break;
      vis[i*p[j]]=1;lpf[i*p[j]]=p[j];
      if(i%p[j]==0) break;
    }
  }For(i,1,n){
    int x=i,y=1;
    while(x>1){
      int now=lpf[x];y*=now;
      while(x%now==0) x/=now;
    }pt[y].emplace_back(i);
  }
}ll ans=0;int tmp[N];
void solve(int id,int lst){
  for(int x within pt[id])
    ans+=(ll)(x+1)*query(x+1);
  For(i,lst,cp){
    if(id*p[i]>=n) break;
    vector<int>lis;
    for(int k=p[i];k<=n;k+=p[i]){
      if(vis[k]) continue;
      int l=pre[k],r=suf[k];
      int x=LCA(pos[l],pos[k]),y=LCA(pos[r],pos[k]);
      if(dfn[x]<dfn[y]) swap(x,y);
      update(T[x].len+1,T[pos[k]].len,-1);
      vis[k]=1;pre[r]=l;suf[l]=r;tmp[k]=x;lis.emplace_back(k);
    }solve(id*p[i],i+1);
    for(int k within lis){
      pre[suf[k]]=k;suf[pre[k]]=k;
      int x=tmp[k];update(T[x].len+1,T[pos[k]].len,1);
      vis[k]=0;
    }
  }
}
signed LJY(){
  n=read();scanf("%s",s+1);siz=sqrt(n+1);init(n);
  if(n==1){puts("1"),exit(0);}
  For(i,1,n) vis[i]=0,pre[i]=i-1,suf[i]=i+1;
  For(i,1,n+1) bel[i]=(i-1)/siz+1;
  For(i,1,n) extend(s[i]-'a'),pos[i]=lst;
  For(i,2,tot) G[T[i].fa].emplace_back(i);
  dfs(1,0);
  For(i,1,31^__builtin_clz(tot)) For(j,1,tot-(1<<i)+1)
    st[i][j]=gmin(st[i-1][j],st[i-1][j+(1<<i-1)]);
  For(i,2,tot) update(T[T[i].fa].len+1,T[i].len,1);
  For(i,1,n) ord[i]=i;
  sort(ord+1,ord+1+n,[&](int x,int y){return dfn[pos[x]]<dfn[pos[y]];});
  For(i,1,n) pre[ord[i]]=ord[i-1],suf[ord[i]]=ord[i+1];
  solve(1,1);printf("%lld",ans+1);
  return 0;
}