#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
    #ifdef ONLINE_JUDGE
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 2e5 + 5;
int cnt, prime[N];
bool visp[N];
void init(int _){
    _rep(i, 2, _){
        if(!visp[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && prime[j] * i <= _; ++j){
            visp[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
int n, id, pos[N], dfn[N], rev[N], f[N][25];
char s[N];
vector<int> G[N];
struct List{
    int top, pre[N], nxt[N];
    struct node{
        int x, val, op;
    }st[N];
    void undo(){if(st[top].op) nxt[st[top].x] = st[top].val; else pre[st[top].x] = st[top].val; top--;}
    void undo(int lst){while(top > lst) undo();}
    void del(int x){
        if(pre[x]) st[++top] = {pre[x], nxt[pre[x]], 1}, nxt[pre[x]] = nxt[x];
        if(nxt[x]) st[++top] = {nxt[x], pre[nxt[x]], 0}, pre[nxt[x]] = pre[x];
    }
}l;
namespace Tree{
    int num = 1, lst = 1;
    struct node{
        int len, link, nxt[26];
    }a[N];
    void insert(int c){
        int cur = ++num, p = lst; a[cur].len = a[p].len + 1;
        while(p && !a[p].nxt[c]) a[p].nxt[c] = cur, p = a[p].link;
        if(!p) a[cur].link = 1;
        else{
            int q = a[p].nxt[c];
            if(a[q].len == a[p].len + 1) a[cur].link = q;
            else{
                int nq = ++num; a[nq] = a[q], a[nq].len = a[p].len + 1;
                while(p && a[p].nxt[c] == q) a[p].nxt[c] = nq, p = a[p].link;
                a[q].link = a[cur].link = nq;
            }
        }
        lst = cur;
    }
    void dfs(int u, int fa){
        f[dfn[u] = ++id][0] = fa, rev[id] = u;
        for(auto &v : G[u]) dfs(v, u);
    }
    int mindfn(int x, int y){return dfn[x] < dfn[y] ? x : y;}
    int lca(int x, int y){
        if(x == y) return x;
        x = dfn[x], y = dfn[y]; if(x > y) swap(x, y); x++;
        int k = __lg(y - x + 1);
        return mindfn(f[x][k], f[y - (1 << k) + 1][k]);
    }
    void build(){
        vector<int> v;
        _rep(i, 1, n) insert(s[i] - 'a'), pos[i] = lst, v.pb(lst);
        _rep(i, 2, num) G[a[i].link].pb(i);
        dfs(1, 0);
        _rep(i, 1, 20) _rep(j, 1, num - (1 << i) + 1) f[j][i] = mindfn(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
        for(auto &i : v) i = dfn[i];
        sort(v.begin(), v.end());
        _rep(i, 0, v.size() - 1) l.pre[v[i]] = !i ? 0 : v[i - 1], l.nxt[v[i]] = i == v.size() - 1 ? 0 : v[i + 1];
    }
}
using Tree::lca;
struct Block{
    const int B = 300;
    #define bel(x) ((x - 1) / B + 1)
    #define L(x) ((x - 1) * B + 1)
    #define R(x) (min(n + 1, x * B))
    int sum[N], c[N];
    void modify(int x, int val){
        sum[bel(x)] += val, c[x] += val;
    }
    void modify(int l, int r, int val){
        modify(l, val), modify(r + 1, -val);
    }
    int ask(int x){
        int ans = 0;
        _rep(i, 1, bel(x) - 1) ans += sum[i];
        _rep(i, L(bel(x)), x) ans += c[i];
        return ans;
    }
}bl;
int c[N];
vector<PII> rem;
void undo(int lst){
    while(rem.size() > lst){
        int L = rem.back().fi, R = rem.back().se; rem.pop_back();
        // _rep(i, L, R) c[i]++;
        bl.modify(L, R, 1);
    }
}
void update(int x){
    int u = l.pre[dfn[x]], v = l.nxt[dfn[x]], t = 1;
    // debug("update x:%d pre:%d nxt:%d ", x, rev[u], rev[v]);
    if(u) u = lca(rev[u], x), t = dfn[u] > dfn[t] ? u : t; 
    if(v) v = lca(rev[v], x), t = dfn[v] > dfn[t] ? v : t;
    int L = Tree::a[t].len + 1, R = Tree::a[x].len;
    l.del(dfn[x]);
    // debug("t:%d L:%d R:%d\n", t, L, R);

    if(L <= R){
        rem.pb({L, R});
        // _rep(i, L, R) c[i]--;
        bl.modify(L, R, -1);
    }
}
ll ans;
bool vis[N];
vector<int> p;
void dfs2(int u, ll cur){
    if(u == p.size()){
        // debug("len:%d num:%d\n", cur + 1, c[cur + 1]);
        // ans += (cur + 1) * c[cur + 1];
        ans += (cur + 1) * bl.ask(cur + 1);
        return;
    }
    for(ll i = cur; i <= n; i *= p[u]) dfs2(u + 1, i);
}
void dfs(int u, ll cur){
    if(u > cnt){
        dfs2(0, cur);
        return;
    }
    if(cur * prime[u] <= n){
        int lst = l.top, lst2 = rem.size(); vector<int> v;
        // debug("cur:%d prime:%d\n", cur, prime[u]);
        for(int i = prime[u]; i <= n; i += prime[u]){
            if(vis[i]) continue;
            vis[i] = 1, update(pos[i]);
            v.pb(i);
        }
        p.pb(prime[u]);
        dfs(u + 1, cur * prime[u]);
        p.pop_back();
        l.undo(lst), undo(lst2);
        for(auto &i : v) vis[i] = 0;
    }
    dfs(u + 1, cur);
}
int main(){
    read(n), scanf("%s", s + 1);
    init(n), Tree::build();
    _rep(i, 2, Tree::num){
        int L = Tree::a[Tree::a[i].link].len + 1, R = Tree::a[i].len;
        // _rep(j, L, R) c[j]++;
        bl.modify(L, R, 1);
    }
    dfs(1, 1);
    writeln(ans + 1);
    return 0;
}