#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;
const int logn = 20;

int n, pr[maxn], tot, m, p[maxn], mpr[maxn], st[logn][maxn], dfn[maxn], tim;
int q[maxn], pre[maxn], nxt[maxn], d[maxn];
char s[maxn];
bool vis[maxn];
vector<int> G[maxn], ps[maxn];

struct SAM {
	int lst, tot, fa[maxn], ch[maxn][26], len[maxn];
	
	inline void init() {
		lst = tot = 1;
	}
	
	inline void insert(int k, int c) {
		int u = ++tot, p = lst;
		lst = u;
		len[u] = k;
		for (; p && !ch[p][c]; p = fa[p]) {
			ch[p][c] = u;
		}
		if (!p) {
			fa[u] = 1;
			return;
		}
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[u] = q;
			return;
		}
		int nq = ++tot;
		fa[nq] = fa[q];
		len[nq] = len[p] + 1;
		memcpy(ch[nq], ch[q], sizeof(ch[nq]));
		fa[u] = fa[q] = nq;
		for (; p && ch[p][c] == q; p = fa[p]) {
			ch[p][c] = nq;
		}
	}
} sam;

void dfs(int u, int fa) {
	dfn[u] = ++tim;
	st[0][tim] = fa;
	for (int v : G[u]) {
		dfs(v, u);
	}
}

inline int get(int i, int j) {
	return dfn[i] < dfn[j] ? i : j;
}

inline int qlca(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 get(st[k][x], st[k][y - (1 << k) + 1]);
}

struct DS {
	int bel[maxn], blo, L[maxn], R[maxn], a[maxn], b[maxn];
	
	inline void init() {
		blo = sqrt(n);
		for (int i = 1; i <= n; ++i) {
			bel[i] = (i - 1) / blo + 1;
			if (!L[bel[i]]) {
				L[bel[i]] = i;
			}
			R[bel[i]] = i;
		}
	}
	
	inline void update(int x, int y) {
		a[x] += y;
		b[bel[x]] += y;
	}
	
	inline void update(int l, int r, int x) {
		l = max(l, 1);
		if (l > r) {
			return;
		}
		update(l, x);
		update(r + 1, -x);
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = 1; i < bel[x]; ++i) {
			res += b[i];
		}
		for (int i = L[bel[x]]; i <= x; ++i) {
			res += a[i];
		}
		return res;
	}
} ds;

ll ans = 1;

void work(int x, int t) {
	// printf("x: %d\n", x);
	for (int i : ps[x]) {
		// printf("i: %d %d\n", i, ds.query(i));
		ans += 1LL * (i + 1) * ds.query(i);
	}
	for (int j = t; j <= tot && 1LL * x * pr[j] < n; ++j) {
		vector<int> S;
		for (int k = pr[j]; k <= n; k += pr[j]) {
			if (vis[k]) {
				continue;
			}
			// printf("del %d\n", k);
			int l = pre[k], r = nxt[k];
			nxt[l] = r;
			pre[r] = l;
			int xx = qlca(p[l], p[k]), yy = qlca(p[k], p[r]);
			if (dfn[xx] < dfn[yy]) {
				swap(xx, yy);
			}
			// printf("upd: %d %d\n", sam.len[xx], sam.len[p[k]]);
			ds.update(sam.len[xx], sam.len[p[k]] - 1, -1);
			vis[k] = 1;
			d[k] = xx;
			S.pb(k);
		}
		work(x * pr[j], j + 1);
		for (int k : S) {
			int l = pre[k], r = nxt[k];
			nxt[l] = pre[r] = k;
			int xx = d[k];
			ds.update(sam.len[xx], sam.len[p[k]] - 1, 1);
			vis[k] = 0;
		}
	}
}

void solve() {
	scanf("%d%s", &n, s + 1);
	if (n == 1) {
		puts("1");
		return;
	}
	sam.init();
	p[0] = 1;
	for (int i = 1; i <= n; ++i) {
		sam.insert(i, s[i] - 'a');
		p[i] = sam.lst;
		q[i] = i;
		// printf("p[%d] = %d\n", i, p[i]);
	}
	m = sam.tot;
	for (int i = 2; i <= m; ++i) {
		G[sam.fa[i]].pb(i);
	}
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) {
			pr[++tot] = i;
			mpr[i] = i;
		}
		for (int j = 1; j <= tot && i * pr[j] <= n; ++j) {
			vis[i * pr[j]] = 1;
			mpr[i * pr[j]] = pr[j];
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		int x = i, y = 1;
		while (x > 1) {
			int t = mpr[x];
			y *= t;
			while (x % t == 0) {
				x /= t;
			}
		}
		ps[y].pb(i);
	}
	dfs(1, 0);
	for (int j = 1; (1 << j) <= m; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
			st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	sort(q + 1, q + n + 1, [&](const int &x, const int &y) {
		return dfn[p[x]] < dfn[p[y]];
	});
	for (int i = 1; i <= n; ++i) {
		pre[q[i]] = q[i - 1];
		nxt[q[i]] = q[i + 1];
	}
	ds.init();
	for (int i = 2; i <= m; ++i) {
		// printf("i: %d %d %d\n", i, sam.len[sam.fa[i]] + 1, sam.len[i]);
		// printf("%d %d\n", sam.fa[i], i);
		ds.update(sam.len[sam.fa[i]], sam.len[i] - 1, 1);
	}
	mems(vis, 0);
	work(1, 1);
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}