#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;


const int MAXN = 100100;
const int W = 25;

int sums[(1 << W) + 228];

struct Btst {
  int vals[MAXN / W];
  Btst() {
    fill(vals, vals + MAXN / W, 0);
  }
  Btst(int len) {
    fill(vals, vals + MAXN / W, 0);
    for (int i = 0; i < len / W; ++i)
      vals[i] = (1 << W) - 1;
    int b = len / W;
    for (int i = 0; i < len - b * W; ++i) {
      vals[b] |= 1 << i;
    }
  }
  void set(int i, int x) {
    if (x == 1) {
      vals[i / W] |= 1 << (i % W);
    } else {
      vals[i / W] &= ~(1 << (i % W));
    }
  }
  Btst& operator&=(const Btst& other) {
    for (int i = 0; i < MAXN / W; ++i)
      vals[i] &= other.vals[i];
    return *this;
  }
  Btst& operator|=(const Btst& other) {
    for (int i = 0; i < MAXN / W; ++i)
      vals[i] |= other.vals[i];
    return *this;
  }
  long long get_sum() const {
    long long ans = 0;
    for (int i = 0; i < MAXN / W; ++i) {
      ans += (i * W) * __builtin_popcount(vals[i]);
      ans += sums[vals[i]];
    }
    return ans;
  }
  bool get(int i) const {
    return 1 & (vals[i / W] >> (i % W));
  }
};


const int K = 337;

Btst precalc[K];

vector<int> primes;
int min_prime[MAXN];


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  for (int x = 0; x < (1 << W); ++x) {
    for (int i = 0; i < W; ++i) {
      if (x & (1 << i))
        sums[x] += i + 1;
    }
  }


  for (int i = 2; i < MAXN; ++i) {
    if (min_prime[i] == 0) {
      min_prime[i] = i;
      primes.emplace_back(i);
    }
    for (int j = 0; j < primes.size() && primes[j] <= min_prime[i] && primes[j] * i < MAXN; ++j)
      min_prime[primes[j] * i] = primes[j];
  }

  for (int i = 0; i < MAXN; ++i)
    precalc[0].set(i, 1);
  precalc[1] = precalc[0];
  for (int i = 2; i < K; ++i) {
    if (min_prime[i] == i) {
      precalc[i] = precalc[0];
      for (int j = 0; j < MAXN; j += i)
        precalc[i].set(j, 0);
    } else {
      precalc[i] = precalc[i / min_prime[i]];
      precalc[i] &= precalc[min_prime[i]];
    }
  }


  int m;
  cin >> m;
  string s;
  //for (int j = 0; j < m; ++j)
  //  s += char('a' + rand() % 3);
  cin >> s;

  s += '$';
  int N = s.size();
  auto safe = [&](int i) {
    if (i >= N)
      return i - N;
    return i;
  };
  vector<int> order(N);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return s[a] < s[b];
  });
  vector<int> classes(N);
  classes[order[0]] = 0;
  for (int i = 1; i < N; ++i)
    classes[order[i]] = classes[order[i - 1]] + (s[order[i]] != s[order[i - 1]]);
  vector<int> new_order(N);
  vector<int> new_classes(N);
  vector<int> cnt(N);
  for (int l = 1; l < N; l *= 2) {
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = 0; i < N; ++i)
      ++cnt[classes[i]];
    for (int i = 1; i < N; ++i)
      cnt[i] += cnt[i - 1];
    for (int i = N - 1; i >= 0; --i) {
      int j = order[i] - l;
      if (j < 0)
        j += N;
      --cnt[classes[j]];
      new_order[cnt[classes[j]]] = j;
    }
    new_classes[new_order[0]] = 0;
    for (int i = 1; i < N; ++i)
      new_classes[new_order[i]] = new_classes[new_order[i - 1]] + (make_pair(classes[new_order[i]], classes[safe(new_order[i] + l)]) != 
        make_pair(classes[new_order[i - 1]], classes[safe(new_order[i - 1] + l)]));
    swap(classes, new_classes);
    swap(order, new_order);
  }
  
  vector<int> lcp(N);
  int tmp = 0;
  vector<int> id(N);
  for (int i = 0; i < N; ++i)
    id[order[i]] = i;
  for (int i = 0; i < N; ++i) {
    if (id[i] == N - 1) {
      tmp = 0;
      continue;
    }
    int j = id[i];
    while (s[i + tmp] == s[order[j + 1] + tmp])
      ++tmp;
    lcp[j] = tmp;
    tmp = max(tmp - 1, 0);
  }

  Btst alive;
  Btst cur;
  long long ans = 0;

  for (int i = 0; i < N; ++i) {
    int l = order[i] + 1;
    int len = N - l;

    cur = precalc[0];
    for (int j = K - 1; j > 1; --j) {
      if (l % j == 0) {
        cur &= precalc[j];
        l /= j;
      }
    }
    if (l > 1) {
      for (int j = 0; j < MAXN; j += l)
        cur.set(j, 0);
    }

    alive |= cur;
    alive &= Btst(len);
    ans += alive.get_sum();
    alive &= Btst(lcp[i]);
    ans -= alive.get_sum();
  }
  cout << ans << '\n';
  return 0;
}