#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, B = 6;

vector <vector<int> > subs[N];
vector <int> g[N];
int isp[N], cnt[20];
char c[N];
int n;

struct sam_t {
	int ch[N][26], len[N], fa[N], pos[N];
	int cnt, las;
	
	void init() {
		cnt = las = 1;
	}
	
	void extend(int x, int id) {
		int p = las, np = las = ++cnt; len[np] = len[p] + 1;
		for (; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
		if (!p) fa[np] = 1;
		else {
			int q = ch[p][x];
			if (len[q] == len[p] + 1) fa[np] = q;
			else {
				int nq = ++cnt; len[nq] = len[p] + 1;
				memcpy(ch[nq], ch[q], sizeof(ch[q]));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for (; ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
			}
		}
		pos[np] = id;
	}
} sam;

vector <int> adj[N], vec[N];
map <vector <int>, int> mp, all;
int mpcnt; long long ans;

const int M = N * 200;

struct seg_t {
	int rt[N], lc[M], rc[M], sum[M], tot;
	void ins(int &u, int pre, int l, int r, int x) {
		u = ++tot; lc[u] = lc[pre]; rc[u] = rc[pre]; sum[u] = sum[pre] + 1;
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (mid >= x) ins(lc[u], lc[pre], l, mid, x);
		else ins(rc[u], rc[pre], mid + 1, r, x);
	}
	
	int query(int u, int l, int r, int x) {
		if (!u) return 0;
		if (l == r) return sum[u];
		int mid = (l + r) >> 1;
		if (mid >= x) return query(lc[u], l, mid, x);
		return query(rc[u], mid + 1, r, x);
	}
} tr;

vector < vector <int> > res[N];
int tops[N], pre[N], siz[N], fa[N];
int dfnt;
void dfs1(int u) {
	if (sam.pos[u]) {
		tops[u] = ++dfnt; pre[dfnt] = u;
		siz[u] = 1;
	} else {
		tops[u] = dfnt + 1;
		siz[u] = 0;
	}
	for (auto v : adj[u]) {
		dfs1(v);
		siz[u] += siz[v];
	}
}

bool cmp(vector <int> a, vector <int> b) {
	return a.size() < b.size();
}

vector <int> merge(vector <int> a, vector <int> b) {
	for (auto i : b) a.push_back(i);
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	return a;
}

void add(int u, int coef) {
	/*
	fprintf(stderr, "u : %d\n", u);
	for (auto i : res[u]) {
		fprintf(stderr, "{");
		for (auto j : i) fprintf(stderr, "%d, ", j);
		fprintf(stderr, "}\n");
	}
	*/
	int len = (int)res[u].size() - 1;
	while (len >= 0 && res[u][len].size() == B) {
		all[res[u][len]] += coef;
		--len;
	}
	auto dfs = [&](auto self, int i, vector <int> vec, int coef) {
		if (i == len + 1 || (int)vec.size() == B) {
			all[vec] += coef;
			return;
		}
		self(self, i + 1, vec, coef);
		vec = merge(vec, res[u][i]);
		if ((int)vec.size() <= B) self(self, i + 1, vec, -coef);
	};
	dfs(dfs, 0, {}, coef);
}

int main() {
	for (int i = 2; i <= N - 5; i++) {
		if (!isp[i]) {
			for (int j = i; j <= N - 5; j += i) {
				g[j].push_back(i);
				if (i != j) isp[j] = 1;
			}
		}
	}
	sam.init();
	scanf("%d%s", &n, c + 1);
	
	for (int i = 1; i <= n; i++) {
		auto dfs = [&](auto self, int u, vector <int> vec) {
			if (u == (int)g[i].size()) {
				subs[i].push_back(vec);
				return;
			}
			self(self, u + 1, vec);
			if ((int)vec.size() < B) {
				vec.push_back(g[i][u]);
				self(self, u + 1, vec);
			}
			return;
		};
		dfs(dfs, 0, {});
		for (auto j : subs[i]) {
			if (!mp.count(j)) {
				mp[j] = ++mpcnt;
			}
		}
	}
	
	for (int i = 1; i <= n; i++) sam.extend(c[i] - 'a', i);
	for (int i = 2; i <= sam.cnt; i++) {
		adj[sam.fa[i]].push_back(i);
		vec[sam.len[i]].push_back(i);
	}
	dfs1(1);
	for (int i = 1; i <= n; i++) {
		tr.rt[i] = tr.rt[i - 1];
		for (auto j : subs[pre[i]]) {
			if (!j.size()) continue;
			tr.ins(tr.rt[i], tr.rt[i], 1, mpcnt, mp[j]);
		}
	}
	ans = 1;
	for (int i = n; i >= 2; i--) {
		for (auto j : vec[i]) {
			int u = j;
			for (auto v : adj[u]) {
				add(v, -1);
			}
			auto dfs = [&](auto self, vector <int> vec) {
				sort(vec.begin(), vec.end());
				int l = tops[u], r = tops[u] + siz[u] - 1, res = -1;
				// fprintf(stderr, "u = %d, l = %d, r  = %d\n", u, l, r);
				while (l <= r) {
					int mid = (l + r) >> 1, cnt = 0;
					// check [tops[u], mid]
					for (int mask = 0; mask < (1 << vec.size()); mask++) {
						vector <int> now;
						for (int j = 0; j < (int)vec.size(); j++) {
							if ((mask >> j) & 1) {
								now.push_back(vec[j]);
							}
						}
						if (!mp.count(now)) continue;
						int coef = __builtin_popcount(mask) % 2 ? 1 : -1;
						cnt += coef * (tr.query(tr.rt[mid], 1, mpcnt, mp[now]) - tr.query(tr.rt[tops[u] - 1], 1, mpcnt, mp[now]));
					}
					// fprintf(stderr, "l = %d, r = %d, mid = %d, cnt = %d\n", l, r, mid, cnt);
					if (cnt != mid - tops[u] + 1) res = mid, r = mid - 1;
					else l = mid + 1;
				}
				if (res == -1) {
					::res[u].push_back(vec);
					return;
				}
				if (vec.size() == B) return;
				for (auto i : g[pre[res]]) {
					vector <int> nvec = vec;
					int ok = 1;
					for (auto j : vec) {
						if (i == j) {
							ok = 0;
							break;
						}
					}
					if (!ok) continue;
					nvec.push_back(i);
					self(self, nvec);
				}
				return;
			};
			dfs(dfs, {});
			add(u, 1);
		}
		if ((int)g[i].size() <= B) {
			for (int mask = 0; mask < (1 << g[i - 1].size()); mask++) {
				vector <int> vec;
				for (int j = 0; j < (int)g[i - 1].size(); j++) {
					if ((mask >> j) & 1) {
						vec.push_back(g[i - 1][j]);
					}
				}
				if (all.count(vec)) ans += all[vec] * i;
			}
		}
		// fprintf(stderr, "i = %d, ans = %lld\n", i, ans);
	}
	printf("%lld\n", ans);
	return 0;
}