#include <bits/stdc++.h>
using namespace std;
set<pair<int, int> > s[1000005];
int bio[1000005], r[1000005], arr[1000005];
vector<pair<int, int> > veki[1000005];
char b[1000005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 2; i <= 1000000; i++) {
    if (!bio[i]) {
      for (int j = i; j <= 1000000; j += i) {
        bio[j] = 1;
        int v = j;
        int br = 0;
        while (v % i == 0) {
          v /= i;
          br++;
        }
        veki[j].push_back(make_pair(i, br));
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  long long sol = 0ll;
  for (int i = n; i > 0; i--) {
    if (b[i] == '/' and arr[i] > 1) {
      r[i] = i;
      continue;
    }
    if (b[i] == '*') {
      for (auto v : veki[arr[i]]) {
        s[i].insert(v);
      }
    }
    int j = i + 1;
    r[i] = i + 1;
    while (j <= n) {
      if (r[j] > j) {
        if (s[j].size() > s[i].size()) swap(s[i], s[j]);
        while (s[j].size()) {
          pair<int, int> p = *s[j].begin();
          s[j].erase(s[j].begin());
          auto it = s[i].lower_bound(make_pair(p.first, 0));
          if (it == s[i].end() or (*it).first > p.first)
            s[i].insert(p);
          else {
            p.second += (*it).second;
            s[i].erase(it);
            s[i].insert(p);
          }
        }
        j = r[j];
      } else {
        int tr = 1;
        for (auto v : veki[arr[j]]) {
          auto it = s[i].lower_bound(make_pair(v.first, 0));
          if (it == s[i].end() or (*it).first > v.first) {
            tr = 0;
            break;
          }
          if ((*it).second < v.second) {
            tr = 0;
            break;
          }
        }
        if (!tr) {
          break;
        } else {
          for (auto v : veki[arr[j]]) {
            auto it = s[i].lower_bound(make_pair(v.first, 0));
            pair<int, int> p = make_pair(v.first, (*it).second - v.second);
            s[i].erase(it);
            s[i].insert(p);
          }
          j++;
        }
      }
    }
    r[i] = j;
  }
  for (int i = 1; i <= n; i++) {
    sol += r[i] - i;
  }
  cout << sol;
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

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>
using namespace std;
set<pair<int, int> > s[1000005];
int bio[1000005], r[1000005], arr[1000005];
vector<pair<int, int> > veki[1000005];
char b[1000005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 2; i <= 1000000; i++) {
    if (!bio[i]) {
      for (int j = i; j <= 1000000; j += i) {
        bio[j] = 1;
        int v = j;
        int br = 0;
        while (v % i == 0) {
          v /= i;
          br++;
        }
        veki[j].push_back(make_pair(i, br));
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  long long sol = 0ll;
  for (int i = n; i > 0; i--) {
    if (b[i] == '/' and arr[i] > 1) {
      r[i] = i;
      continue;
    }
    if (b[i] == '*') {
      for (auto v : veki[arr[i]]) {
        s[i].insert(v);
      }
    }
    int j = i + 1;
    r[i] = i + 1;
    while (j <= n) {
      if (r[j] > j) {
        if (s[j].size() > s[i].size()) swap(s[i], s[j]);
        while (s[j].size()) {
          pair<int, int> p = *s[j].begin();
          s[j].erase(s[j].begin());
          auto it = s[i].lower_bound(make_pair(p.first, 0));
          if (it == s[i].end() or (*it).first > p.first)
            s[i].insert(p);
          else {
            p.second += (*it).second;
            s[i].erase(it);
            s[i].insert(p);
          }
        }
        j = r[j];
      } else {
        int tr = 1;
        for (auto v : veki[arr[j]]) {
          auto it = s[i].lower_bound(make_pair(v.first, 0));
          if (it == s[i].end() or (*it).first > v.first) {
            tr = 0;
            break;
          }
          if ((*it).second < v.second) {
            tr = 0;
            break;
          }
        }
        if (!tr) {
          break;
        } else {
          for (auto v : veki[arr[j]]) {
            auto it = s[i].lower_bound(make_pair(v.first, 0));
            pair<int, int> p = make_pair(v.first, (*it).second - v.second);
            s[i].erase(it);
            s[i].insert(p);
          }
          j++;
        }
      }
    }
    r[i] = j;
  }
  for (int i = 1; i <= n; i++) {
    sol += r[i] - i;
  }
  cout << sol;
  return 0;
}

```