#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
struct SAM {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        std::array<int, ALPHABET_SIZE> next;
        Node() : len{}, link{}, next{} {}
    };
    std::vector<Node> t;
    SAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        if (t[p].next[c]) {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1) {
                return q;
            }
            int r = newNode();
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            t[r].next = t[q].next;
            t[q].link = r;
            while (t[p].next[c] == q) {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = newNode();
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c]) {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        return cur;
    }
    int extend(int p, char c, char offset = 'a') {
        return extend(p, c - offset);
    }
    
    int next(int p, int x) {
        return t[p].next[x];
    }
    
    int next(int p, char c, char offset = 'a') {
        return next(p, c - 'a');
    }
    
    int link(int p) {
        return t[p].link;
    }
    
    int len(int p) {
        return t[p].len;
    }
    
    int size() {
        return t.size();
    }
};
std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    sieve(n);
    
    std::string s;
    std::cin >> s;
    
    SAM sam;
    int p = 1;
    std::vector<int> endpos(n + 1);
    endpos[0] = 1;
    for (int i = 0; i < n; i++) {
        p = sam.extend(p, s[i]);
        endpos[i + 1] = p;
    }
    
    i64 ans = 0;
    
    const int N = sam.size();
    
    std::vector<std::vector<int>> adj(N);
    for (int i = 2; i < N; i++) {
        adj[sam.link(i)].push_back(i);
    }
    
    int cur = 0;
    std::vector<int> in(N), ord(N);
    
    auto dfs = [&](auto &self, int x) -> void {
        in[x] = ++cur;
        ord[in[x]] = x;
        for (auto y : adj[x]) {
            self(self, y);
        }
    };
    dfs(dfs, 1);
    
    const int logN = std::__lg(N);
    std::vector rmq(logN + 1, std::vector<int>(N));
    for (int i = 1; i < N - 1; i++) {
        rmq[0][i] = in[sam.link(ord[i + 1])];
    }
    
    for (int j = 0; j < logN; j++) {
        for (int i = 1; i + (2 << j) <= N - 1; i++) {
            rmq[j + 1][i] = std::min(rmq[j][i], rmq[j][i + (1 << j)]);
        }
    }
    
    auto lca = [&](int x, int y) {
        if (x == y) {
            return x;
        };
        x = in[x];
        y = in[y];
        if (x > y) {
            std::swap(x, y);
        }
        int k = std::__lg(y - x);
        return ord[std::min(rmq[k][x], rmq[k][y - (1 << k)])];
    };
    
    std::vector<std::vector<int>> lens(n);
    for (int l = 1; l < n; l++) {
        int x = l;
        int a = 1;
        while (x > 1) {
            int p = minp[x];
            while (x % p == 0) {
                x /= p;
            }
            a *= p;
        }
        lens[a].push_back(l);
    }
    
    std::vector<int> L(n + 1), R(n + 1);
    std::vector<int> orde(n);
    std::iota(orde.begin(), orde.end(), 1);
    std::sort(orde.begin(), orde.end(),
        [&](int i, int j) {
            return in[endpos[i]] < in[endpos[j]];
        });
    for (int i = 1; i < n; i++) {
        R[orde[i - 1]] = orde[i];
        L[orde[i]] = orde[i - 1];
    }
    R[orde[n - 1]] = orde[0];
    L[orde[0]] = orde[n - 1];
    const int B = std::sqrt(n);
    std::vector<int> sum(n / B + 1), a(n);
    auto add = [&](int x, int v) {
        a[x] += v;
        sum[x / B] += v;
    };
    auto query = [&](int x) {
        int xb = x / B;
        int res = 0;
        for (int i = 0; i < xb; i++) {
            res += sum[i];
        }
        for (int i = xb * B; i <= x; i++) {
            res += a[i];
        }
        return res;
    };
    for (int i = 2; i < N; i++) {
        add(sam.len(sam.link(i)), 1);
        add(sam.len(i), -1);
    }
    
    std::vector<int> dtm(n + 1), dl(n + 1), dr(n + 1), da(n + 1);
    auto rec = [&](auto &self, int v, int i) -> void {
        for (auto l : lens[v]) {
            ans += 1LL * (l + 1) * query(l);
            // std::cerr << l + 1 << " " << query(l) << "\n";
        }
        for (int j = i; j < primes.size() && 1LL * v * primes[j] < n; j++) {
            for (int x = primes[j]; x <= n; x += primes[j]) {
                int l = L[x], r = R[x];
                if (l || r) {
                    dtm[x] = v;
                    dl[x] = l;
                    dr[x] = r;
                    if (l) {
                        R[l] = r;
                    }
                    if (r) {
                        L[r] = l;
                    }
                    L[x] = 0;
                    R[x] = 0;
                    int a = lca(endpos[l], endpos[x]);
                    int b = lca(endpos[x], endpos[r]);
                    if (in[a] < in[b]) {
                        std::swap(a, b);
                    }
                    da[x] = a;
                    add(sam.len(a), -1);
                    add(sam.len(endpos[x]), 1);
                }
            }
            self(self, v * primes[j], j + 1);
            for (int x = primes[j]; x <= n; x += primes[j]) {
                if (dtm[x] == v) {
                    int l = dl[x];
                    int r = dr[x];
                    if (l) {
                        R[l] = x;
                    }
                    if (r) {
                        L[r] = x;
                    }
                    L[x] = l;
                    R[x] = r;
                    add(sam.len(da[x]), 1);
                    add(sam.len(endpos[x]), -1);
                }
            }
        }
    };
    rec(rec, 1, 0);
    
    ans++;
    std::cout << ans << "\n";
    
    return 0;
}