#line 1 "C.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

#line 2 "/home/sigma/comp/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 1 "/home/sigma/comp/library/string/suffix_array.hpp"
/*
	SA-IS + LCP

	SuffixArray SA(V<int,ll>) もしくは SA(string)
	でSA.sa,isa,lcpに入る

	[0,N]   sa[i] = i番目に小さいものは s[ sa[i],N ) なので sa[0] = N
	[0,N]   isa[i] = s[i,N) が何番目にいるか
	[0,N-1] lcp[i] = s[ sa[i],N ) と s[ sa[i+1],N ) のlcp lcp[0] = 0
	任意のprefix同士のlcpがsegtree_minで求まる
	あるsubstringが何回出てくるか? とか

	s = abcabac

		(eps)
		abac
		abcabac
		ac
		bac
		bcabac
		c
		cabac
*/

struct SuffixArray{
	V<int> sa;
	V<int> isa;
	V<int> lcp;

	template<class T>
	SuffixArray(const vector<T>& s){	//int,ll
		int N = s.size();
		T s_arr[N];
		rep(i,N) s_arr[i] = s[i];
		int sa_arr[N+1];
		int lcp_arr[N];
		{	//zaatsu
			V<T> vs = s;
			sort(all(vs));
			vs.erase(unique(all(vs)),vs.end());
			rep(i,N) s_arr[i] = lower_bound(all(vs),s[i]) - vs.begin();
		}
		int K = N;
		SA(N,s_arr,sa_arr,K);
		LCP(N,s_arr,sa_arr,lcp_arr);
		sa = V<int>(sa_arr,sa_arr+(N+1));
		isa.resize(N+1);
		rep(i,N+1) isa[sa[i]] = i;
		lcp = V<int>(lcp_arr,lcp_arr+N);
	}
	SuffixArray(const string& s){
		int N = s.size();
		char s_arr[N];
		rep(i,N) s_arr[i] = s[i];
		int sa_arr[N+1];
		int lcp_arr[N];
		SA(N,s_arr,sa_arr,256);
		LCP(N,s_arr,sa_arr,lcp_arr);
		sa = V<int>(sa_arr,sa_arr+(N+1));
		isa.resize(N+1);
		rep(i,N+1) isa[sa[i]] = i;
		lcp = V<int>(lcp_arr,lcp_arr+N);
	}

	private:

	template<class T>
	void induce(int N,const T s[],bool is[],int sa[],int lbase[],int K){
		int it[K+1];
		copy_n(lbase,K+1,it);
		rep(i,N+1){
			if(sa[i]>=1&&!is[sa[i]-1]){
				int c=s[sa[i]-1];
				sa[it[c]++]=sa[i]-1;
			}
		}
		copy_n(lbase,K+1,it);
		for(int i=N;i>0;i--){
			if(sa[i]>=1&&is[sa[i]-1]){
				int c=s[sa[i]-1];
				sa[--it[c+1]]=sa[i]-1;
			}
		}
	}
	template<class T>
	void SA(int N,const T s[],int sa[],int K){
		bool is[N+1];		//stype?
		int lcnt[K+1]={},scnt[K+1]={};
		is[N]=1;
		for(int i=N-1;i>=0;i--){
			if(i==N-1||s[i]>s[i+1]) is[i]=0;
			else if(s[i]<s[i+1]) is[i]=1;
			else is[i]=is[i+1];
			if(!is[i]) lcnt[(int)s[i]]++;
			else scnt[(int)s[i]]++;
		}
		vector<int> v;		//LMSs
		int lms[N+1];
		fill_n(lms,N+1,-1);
		int c=0;
		rep1(i,N-1){
			if(!is[i-1]&&is[i]){
				lms[i]=c++;
				v.pb(i);
			}
		}
		int lbase[K+1],sbase[K+1];
		lbase[0]=1,sbase[0]=1+lcnt[0];
		rep1(i,K){
			lbase[i]=sbase[i-1]+scnt[i-1];
			sbase[i]=lbase[i]+lcnt[i];
		}
		if(!v.empty()){
			vector<int> v2=v;
			int it[K+1];			//iterate
			copy_n(sbase,K+1,it);
			fill_n(sa,N+1,-1);
			sa[0]=N;
			rep(i,v.size()){
				int c=s[v[i]];
				sa[it[c]++]=v[i];
			}
			induce(N,s,is,sa,lbase,K);
			int c=0;
			rep1(i,N) if(lms[sa[i]]>=0) v[c++]=sa[i];
			int s2[v.size()],sa2[v.size()+1];
			c=0;
			s2[lms[v[0]]]=0;
			for(int i=1;i<(int)v.size();i++){
				int l=v[i-1],r=v[i];
				while(true){
					if(l == N || r == N || s[l] != s[r]){
						c++;
						break;
					}
					l++,r++;
					if(lms[l]>=0||lms[r]>=0){
						if(lms[l]<0||lms[r]<0) c++;
						break;
					}
				}
				s2[lms[v[i]]]=c;
			}
			SA(v.size(),s2,sa2,c);
			rep1(i,v.size()) v[i-1]=v2[sa2[i]];
		}
		int it[K+1];
		copy_n(sbase,K+1,it);
		fill_n(sa,N+1,-1);
		sa[0]=N;
		rep(i,v.size()){
			int c=s[v[i]];
			sa[it[c]++]=v[i];
		}
		induce(N,s,is,sa,lbase,K);
	}
	template<class T>
	void LCP(int N,const T s[],const int sa[],int lcp[]){
		int isa[N+1];
		rep(i,N+1) isa[sa[i]]=i;
		int h=0;
		rep(i,N){
			int j=sa[isa[i]-1];
			if(h>0) h--;
			for(;j+h<N&&i+h<N;h++){
				if(s[j+h]!=s[i+h]) break;
			}
			lcp[isa[i]-1]=h;
		}
	}
};
#line 1 "/home/sigma/comp/library/string/suffix_tree.hpp"
/*
	suffix tree

	S = aabbabbaa

	suffix array
	---------
	a--------
	aa-------
	aabbabbaa
	abbaa----
	abbabbaa-
	baa------
	babbaa---
	bbaa-----
	bbabbaa--

	suffix tree の node はこの長方形領域を表す index は preorder (だし、辞書順で早いほうが先)
	---------
	1--------
	12-------
	123333333
	14445----
	14446666-
	789------
	78AAAA---
	7BBC-----
	7BBDDDD--

	例えば node 4 は、 ud[4,6) * lr[1,4) = bba

	初期化:
		SuffixTree(SuffixArray) で諸々を計算
	dat:
		上述の長方形の {u, d, l, r}		0 <= u < d <= sLen+1, 0 <= l <= r <= sLen
		v = 0 でだけ l = r になるので注意 (iff)
		例えば、dat[4] = {4, 6, 1, 4}, dat[0] = {0, sLen+1, 0, 0}
	G:
		suffix tree としての(有向)辺
		例えば G[4] = {5,6}, G[0] = {1,7}
	endpos:
		頂点 v が s[i,N) に対応するならば、endpos[v] = i. ないなら -1
		例えば endpos[4] = -1, endpos[2] = 7, endpos[0] = sLen

	debug(string s):
		元の文字列を渡して↑の情報をわかりやすく出力
*/

#line 1 "/home/sigma/comp/library/ds/cartesian_tree.hpp"
/*
	cartesian tree
	一番小さいところで i 分けて、左右に分割
	range[i] = [l,r) の min/max が A[i]
	[l,i) の min が lch[i], [i+1,r) の min が rch[i] 空なら -1
	一番小さいとこが root

	tie-break は辞書順
*/
template<class T, bool is_min>
struct CartesianTree {
	int N;
	vector<T> A;
	vector<pair<int,int>> range;
	vector<int> lch,rch,par;
	int root;

	CartesianTree(const vector<T>& A_): N(A_.size()), A(A_), range(N), lch(N,-1), rch(N,-1), par(N,-1){
		auto less = [&](int i, int j) -> bool {
			if(is_min) return (A[i] < A[j]) || (A[i] == A[j] && i < j);
			return (A[i] > A[j]) || (A[i] == A[j] && i < j);
		};
		vector<int> st;
		rep(i,N){
			while(!st.empty() && less(i, st.back())){
				lch[i] = st.back();
				st.pop_back();
			}
			range[i].first = (st.empty() ? 0 : st.back() + 1);
			st.eb(i);
		}
		st.clear();
		per(i,N){
			while(!st.empty() && less(i, st.back())){
				rch[i] = st.back();
				st.pop_back();
			}
			range[i].second = (st.empty() ? N : st.back());
			st.eb(i);
		}
		rep(i,N){
			if(lch[i] != -1) par[lch[i]] = i;
			if(rch[i] != -1) par[rch[i]] = i;
		}
		rep(i,N) if(par[i] == -1) root = i;
	}

	/*
		(l, r, h)
		l <= i < r
		h[i] をできるだけ左右に伸ばした時の長方形
	*/
	tuple<int, int, T> maximum_rectangle(int i){
		return {range[i].first, range[i].second, A[i]};
	}
};
#line 51 "/home/sigma/comp/library/string/suffix_tree.hpp"

template<class SuffixArray>
struct SuffixTree {
	struct Node {
		int u, d, l, r;
		friend ostream& operator<<(ostream &o, const Node& x){
			return o << "ud[" << x.u << "," << x.d << ") * lr[" << x.l << "," << x.r << ")";
		}
	};

	const SuffixArray& SA;

	vector<Node> dat;
	vector<vector<int>> G;
	V<int> endpos;

	SuffixTree(const SuffixArray& SA_):SA(SA_){
		const auto& sa = SA.sa;
		const auto& lcp = SA.lcp;
		int sLen = lcp.size();
		CartesianTree<int, true> CT(SA.lcp);

		auto dfs = [&](auto&& self, int idx, int par, int baseh) -> void {
			int L = CT.range[idx].first;
			int R = CT.range[idx].second + 1;
			int h = lcp[idx];
			if(par == -1 || baseh < h){
				if(par != -1) G[par].eb(dat.size());
				par = dat.size();
				dat.eb(L, R, baseh, h); G.pb({}); endpos.pb(-1);
			}
			if(CT.lch[idx] == -1){
				int len = sLen - sa[idx];
				if(h < len){
					G[par].eb(dat.size());
					dat.eb(idx, idx+1, h, len); G.pb({}); endpos.pb(sa[idx]);
				}else{
					endpos.back() = sa[idx];
				}
			}else{
				self(self, CT.lch[idx], par, h);
			}
			if(CT.rch[idx] == -1){
				int len = sLen - sa[idx+1];
				G[par].eb(dat.size());
				dat.eb(idx+1, idx+2, h, len); G.pb({}); endpos.pb(sa[idx+1]);
			}else{
				self(self, CT.rch[idx], par, h);
			}
		};
		dfs(dfs, 0, -1, 0);
	}

	void debug(string s){
		int M = dat.size();
		cerr << "--------- suffix tree debug start ---------" << endl;

		rep(i,s.size()+1) cerr << s.substr(SA.sa[i]) << endl; 
		cerr << endl;

		rep(v,M){
			int off = SA.sa[dat[v].u];
			cerr << "id = " << v << " : " << dat[v] << " = " << s.substr(off + dat[v].l, dat[v].r-dat[v].l) << endl;
		}
		cerr << endl;

		rep(v,M){
			cerr << "children of " << v << " : ";
			for(int u: G[v]) cerr << u << ", ";
			cerr << endl;
		}
		cerr << endl;
		cerr << "endpos " << endpos << endl;
		cerr << endl;
		cerr << "--------- suffix tree debug end ---------" << endl;
	}
};
#line 1 "/home/sigma/comp/library/misc/highbit.hpp"
/*
	x       0  1  2  3  4  5  6  7  8  9
	msb(x) -1  0  1  1  2  2  2  2  3  3
	最上位bit
*/
int highbit(int x){
	return 31 - countl_zero<uint>(x);
}
int highbit(uint x){
	return 31 - countl_zero<uint>(x);
}
int highbit(ll x){
	return 63 - countl_zero<ull>(x);
}
int highbit(ull x){
	return 63 - countl_zero<ull>(x);
}

/*
	x       0  1  2  3  4  5  6  7  8  9
	lsb(x) 32  0  1  0  2  0  1  0  3  0
	最下位bit
*/
int lowbit(int x){
	return countr_zero<uint>(x);
}
int lowbit(uint x){
	return countr_zero<uint>(x);
}
int lowbit(ll x){
	return countr_zero<ull>(x);
}
int lowbit(ull x){
	return countr_zero<ull>(x);
}
#line 3 "/home/sigma/comp/library/ds/bitset.hpp"

struct Bitset{
	int N;
	vector<ull> a;

	Bitset(int N_ = 0, bool init = false):N(N_){
		int sz = (N + 63) >> 6;
		a.assign(sz, init ? -1 : 0);
		if(N) a.back() >>= (64 * a.size() - N);
	}

	int size(){ return N; }

	Bitset& operator&=(const Bitset& r){
		assert(N == r.N);
		rep(i,a.size()) a[i] &= r.a[i];
		return *this;
	}
	Bitset& operator|=(const Bitset& r){
		assert(N == r.N);
		rep(i,a.size()) a[i] |= r.a[i];
		return *this;
	}
	Bitset& operator^=(const Bitset& r){
		assert(N == r.N);
		rep(i,a.size()) a[i] ^= r.a[i];
		return *this;
	}
	Bitset operator&(const Bitset& r) const { return Bitset(*this) &= r; }
	Bitset operator|(const Bitset& r) const { return Bitset(*this) |= r; }
	Bitset operator^(const Bitset& r) const { return Bitset(*this) ^= r; }
	Bitset operator~() const {
		Bitset r = *this;

	}

	// std::bitset::reference 的なやつ bool が 1 byte なので bool& が... みたいなのを解消できる
	struct Ref{
		ull *p;
		int pos;
		Ref(Bitset& b, int pos_){
			p = b.a.data() + (pos_ >> 6);
			pos = pos_ & 63;
		}
		operator bool() const { return (*p >> pos)&1; }
		Ref& operator=(bool x){
			if(x) *p |= 1ULL << pos;
			else *p &= ~(1ULL << pos);
			return *this;
		}
		void flip(){ *p ^= 1ULL<<pos; }
	};

	Ref operator[](int i){ return Ref(*this, i); }

	void flip(int i){ (*this)[i].flip(); }
	void setall(bool init){
		int sz = (N + 63) >> 6;
		fill(all(a), init ? -1 : 0);
		if(N) a.back() >>= (64 * a.size() - N);
	}

	// >= i
	int next(int i){
		chmax(i, 0);
		if(i >= N) return N;
		int k = i >> 6;
		
		ull x = a[k];
		int s = i & 63;
		x = (x >> s) << s;
		if(x) return (k << 6) | lowbit(x);
		for(int idx = k+1; idx < si(a); idx++) if(a[idx]){
			return (idx << 6) | lowbit(a[idx]);
		}
		return N;
	}
	// <= i
	int prev(int i){
		chmin(i, N-1);
		if(i <= -1) return -1;
		int k = i >> 6;

		if((i&63) < 63){
			ull x = a[k];
			int s = i & 63;
			x &= (1ULL << (s+1)) - 1;
			if(x) return (k << 6) | highbit(x);
			k--;
		}
		per(idx,k+1) if(a[idx]){
			return (idx << 6) | highbit(a[idx]);
		}
		return -1;
	}

	int count_range(int L, int R){
		assert(0 <= L && L <= R && R <= N);
		int cnt = 0;
		while((L<R) && (L&63)) cnt += (*this)[L++];
		while((L<R) && (R&63)) cnt += (*this)[--R];
		int l = L >> 6, r = R >> 6;
		for(int i=l;i<r;i++) cnt += popcount(a[i]);
		return cnt;
	}

	// \sum_{L <= i < R} (b[i] ? i : 0)
	ll sum_range(int L, int R){
		static int buf[1<<8] = {};
		if(buf[2] == 0){
			rep(s,1<<8){
				rep(i,8) if(s&1<<i) buf[s] += i;
			}
		}

		assert(0 <= L && L <= R && R <= N);
		ll sum = 0;
		while((L<R) && (L&63)) if((*this)[L++]) sum += L-1;
		while((L<R) && (R&63)) if((*this)[--R]) sum += R;
		int l = L >> 6, r = R >> 6;
		for(int i=l;i<r;i++){
			rep(k,8){
				sum += buf[(a[i] >> (k*8)) & 255] + popcount<uint>((a[i] >> (k*8)) & 255) * (i << 6 | k << 3);
			}
		}
		return sum;
	}
};
#line 8 "C.cpp"

V<bool> isp;
V<int> pr;
V<int> sf; //smallest factor, sf[9*5*11] = 3
void linear_sieve(int X){		// <= X
	isp = V<bool>(X+1,true); isp[0] = isp[1] = false;
	sf = V<int>(X+1);
	pr.clear();
	for(int i=2;i<=X;i++){
		if(isp[i]){
			pr.pb(i);
			sf[i] = i;
		}
		for(int j=0;i*pr[j]<=X;j++){
			isp[i*pr[j]] = false;
			sf[i*pr[j]] = pr[j];
			if(i%pr[j] == 0) break;
		}
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N; string s; cin >> N >> s;

	SuffixArray SA(s);
	SuffixTree ST(SA);
	// ST.debug(s);

	auto& G = ST.G;
	ll ans = 0;

	linear_sieve(N);
	V<Bitset> bp(N+1);
	for(int p: pr){
		bp[p] = Bitset(N+1, true);
		for(int x=0;x<=N;x+=p) bp[p][x] = false;
	}

	int M = G.size();
	V<int> sz(M);
	per(v,M){
		sz[v] = 1;
		for(int u: G[v]) sz[v] += sz[u];
	}

	Bitset tmp(N+1);
	auto dfs = [&](auto&& self, int v, Bitset& bs) -> void {
		int heavy = -1;
		for(int u: G[v]){
			if(heavy == -1 || sz[heavy] < sz[u]) heavy = u;
		}
		if(heavy != -1){
			self(self,heavy,bs);
		}
		for(int u: G[v]) if(u != heavy){
			// light, log 段しかここを通らない
			Bitset cs(N+1);
			self(self,u,cs);
			bs |= cs;
		}
		if(ST.endpos[v] != -1 && ST.endpos[v] != N){
			int l = ST.endpos[v] + 1;
			tmp.setall(true);
			int x = l;
			while(x != 1){
				int p = sf[x];
				tmp &= bp[p];
				while(x%p == 0) x /= p;
			}
			bs |= tmp;
		}
		if(v){
			// for(int len = ST.dat[v].l+1; len <= ST.dat[v].r; len++){
			// 	if(bs[len-1]) ans += len;
			// }
			int L = ST.dat[v].l, R = ST.dat[v].r;
			// for(int i=L;i<R;i++) if(bs[i]) ans += i+1;
			ans += bs.sum_range(L, R) + bs.count_range(L, R);
		}
		return;
	};
	Bitset bs(N+1);
	dfs(dfs,0,bs);
	cout << ans << endl;
}