#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn = 1e6 + 5;
int n;
bool used[maxn];
vector<int> v[maxn];
vector<int> g[maxn];
int ans[maxn];
int pr[maxn];
int t[4 * maxn];
void init() {
  used[0] = true;
  used[1] = true;
  for (int i = 2; i < maxn; ++i) {
    if (used[i]) continue;
    v[i] = {i};
    for (int j = 2 * i; j < maxn; j += i) {
      used[j] = true;
      v[j].push_back(i);
    }
  }
}
vector<int> slv(vector<pair<int, int> > z) {
  vector<int> f;
  for (auto h : z) f.push_back(h.second);
  pr[0] = 0;
  for (int i = 0; i < f.size(); ++i) pr[i + 1] = pr[i] + f[i];
  stack<pair<int, int> > o;
  for (int i = 0; i <= f.size(); ++i) ans[i] = 1e9;
  for (int i = 0; i <= f.size(); ++i) {
    while (true) {
      if (o.empty()) {
        o.push({pr[i], i});
        break;
      }
      pair<int, int> z = o.top();
      if (z.first <= pr[i]) {
        o.push({pr[i], i});
        break;
      } else {
        ans[z.second] = i;
        o.pop();
      }
    }
  }
  vector<int> res;
  for (int i = 0; i < f.size(); ++i) {
    if (ans[i] == 1e9)
      res.push_back(n);
    else
      res.push_back(z[ans[i] - 1].first);
  }
  return res;
}
void to(int node, int tl, int tr, int l, int r, int val) {
  if (tl >= l && tr <= r) {
    t[node] = min(t[node], val);
    return;
  }
  if (tl >= r || tr <= l) {
    return;
  }
  int tm = (tl + tr) / 2;
  to(2 * node + 1, tl, tm, l, r, val);
  to(2 * node + 2, tm, tr, l, r, val);
}
int get(int node, int tl, int tr, int pos) {
  if (tl > pos || tr <= pos) return 1e9;
  int ans = t[node];
  if ((tr - tl) == 1) return ans;
  int tm = (tl + tr) / 2;
  ans = min(ans, get(2 * node + 1, tl, tm, pos));
  ans = min(ans, get(2 * node + 2, tm, tr, pos));
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0; i < 4 * maxn; ++i) t[i] = 1e9;
  init();
  cin >> n;
  int a[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  string s;
  cin >> s;
  for (int i = 0; i < n; ++i)
    for (auto h : v[a[i]]) g[h].push_back(i);
  vector<pair<pair<int, int>, int> > o;
  for (int i = 2; i < maxn; ++i) {
    if (g[i].empty()) continue;
    vector<pair<int, int> > z;
    int o1 = 0;
    for (auto j : g[i]) {
      o1 = 0;
      int x = a[j];
      assert(x % i == 0);
      while (x % i == 0) {
        ++o1;
        x /= i;
      }
      if (s[j] == '*')
        z.push_back({j, o1});
      else
        z.push_back({j, -o1});
    }
    vector<int> t = slv(z);
    for (int i = 0; i < z.size(); ++i) {
      if (i == 0)
        o.push_back({{0, z[0].first + 1}, t[i]});
      else
        o.push_back({{z[i - 1].first + 1, z[i].first + 1}, t[i]});
    }
  }
  to(0, 0, n, 0, n, n);
  for (auto l : o) to(0, 0, n, l.first.first, l.first.second, l.second);
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    int val = get(0, 0, n, i);
    res += max(0, val - i);
  }
  cout << res << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Kuzya started going to school. He was given math homework in which he was given an array a of length n and an array of symbols b of length n, consisting of symbols '*' and '/'.

Let's denote a path of calculations for a segment [l; r] (1 ≤ l ≤ r ≤ n) in the following way: 

  * Let x=1 initially. For every i from l to r we will consequently do the following: if b_i= '*', x=x*a_i, and if b_i= '/', then x=(x)/(a_i). Let's call a path of calculations for the segment [l; r] a list of all x that we got during the calculations (the number of them is exactly r - l + 1). 



For example, let a=[7, 12, 3, 5, 4, 10, 9], b=[/, *, /, /, /, *, *], l=2, r=6, then the path of calculations for that segment is [12, 4, 0.8, 0.2, 2].

Let's call a segment [l;r] simple if the path of calculations for it contains only integer numbers. 

Kuzya needs to find the number of simple segments [l;r] (1 ≤ l ≤ r ≤ n). Since he obviously has no time and no interest to do the calculations for each option, he asked you to write a program to get to find that number!

Input

The first line contains a single integer n (2 ≤ n ≤ 10^6).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6).

The third line contains n symbols without spaces between them — the array b_1, b_2 … b_n (b_i= '/' or b_i= '*' for every 1 ≤ i ≤ n).

Output

Print a single integer — the number of simple segments [l;r].

Examples

Input


3
1 2 3
*/*


Output


2


Input


7
6 4 10 1 2 15 1
*/*/*//


Output


8

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn = 1e6 + 5;
int n;
bool used[maxn];
vector<int> v[maxn];
vector<int> g[maxn];
int ans[maxn];
int pr[maxn];
int t[4 * maxn];
void init() {
  used[0] = true;
  used[1] = true;
  for (int i = 2; i < maxn; ++i) {
    if (used[i]) continue;
    v[i] = {i};
    for (int j = 2 * i; j < maxn; j += i) {
      used[j] = true;
      v[j].push_back(i);
    }
  }
}
vector<int> slv(vector<pair<int, int> > z) {
  vector<int> f;
  for (auto h : z) f.push_back(h.second);
  pr[0] = 0;
  for (int i = 0; i < f.size(); ++i) pr[i + 1] = pr[i] + f[i];
  stack<pair<int, int> > o;
  for (int i = 0; i <= f.size(); ++i) ans[i] = 1e9;
  for (int i = 0; i <= f.size(); ++i) {
    while (true) {
      if (o.empty()) {
        o.push({pr[i], i});
        break;
      }
      pair<int, int> z = o.top();
      if (z.first <= pr[i]) {
        o.push({pr[i], i});
        break;
      } else {
        ans[z.second] = i;
        o.pop();
      }
    }
  }
  vector<int> res;
  for (int i = 0; i < f.size(); ++i) {
    if (ans[i] == 1e9)
      res.push_back(n);
    else
      res.push_back(z[ans[i] - 1].first);
  }
  return res;
}
void to(int node, int tl, int tr, int l, int r, int val) {
  if (tl >= l && tr <= r) {
    t[node] = min(t[node], val);
    return;
  }
  if (tl >= r || tr <= l) {
    return;
  }
  int tm = (tl + tr) / 2;
  to(2 * node + 1, tl, tm, l, r, val);
  to(2 * node + 2, tm, tr, l, r, val);
}
int get(int node, int tl, int tr, int pos) {
  if (tl > pos || tr <= pos) return 1e9;
  int ans = t[node];
  if ((tr - tl) == 1) return ans;
  int tm = (tl + tr) / 2;
  ans = min(ans, get(2 * node + 1, tl, tm, pos));
  ans = min(ans, get(2 * node + 2, tm, tr, pos));
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0; i < 4 * maxn; ++i) t[i] = 1e9;
  init();
  cin >> n;
  int a[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  string s;
  cin >> s;
  for (int i = 0; i < n; ++i)
    for (auto h : v[a[i]]) g[h].push_back(i);
  vector<pair<pair<int, int>, int> > o;
  for (int i = 2; i < maxn; ++i) {
    if (g[i].empty()) continue;
    vector<pair<int, int> > z;
    int o1 = 0;
    for (auto j : g[i]) {
      o1 = 0;
      int x = a[j];
      assert(x % i == 0);
      while (x % i == 0) {
        ++o1;
        x /= i;
      }
      if (s[j] == '*')
        z.push_back({j, o1});
      else
        z.push_back({j, -o1});
    }
    vector<int> t = slv(z);
    for (int i = 0; i < z.size(); ++i) {
      if (i == 0)
        o.push_back({{0, z[0].first + 1}, t[i]});
      else
        o.push_back({{z[i - 1].first + 1, z[i].first + 1}, t[i]});
    }
  }
  to(0, 0, n, 0, n, n);
  for (auto l : o) to(0, 0, n, l.first.first, l.first.second, l.second);
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    int val = get(0, 0, n, i);
    res += max(0, val - i);
  }
  cout << res << endl;
  return 0;
}

```