#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("avx", "avx2")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 1000005;
struct node {
  int pos, dlt;
};
vector<node> zz[N];
int a[N];
char b[N];
int stk[N], top, n;
int minp[N];
void xxs(int n) {
  for (int i = 2; i <= n; i++) {
    for (int j = i; j <= n; j += i)
      if (!minp[j]) minp[j] = i;
  }
}
int minn[N << 2];
void update(int u, int l, int r, int ql, int qr, int lim) {
  if (ql <= l && r <= qr) {
    ckmin(minn[u], lim);
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid) update((u << 1), l, mid, ql, qr, lim);
  if (qr > mid) update((u << 1 | 1), mid + 1, r, ql, qr, lim);
}
long long ans = 0;
void dfs(int u, int l, int r, int carry) {
  ckmin(carry, minn[u]);
  if (l == r) {
    ans += carry - l + 1;
    return;
  }
  int mid = l + r >> 1;
  dfs((u << 1), l, mid, carry);
  dfs((u << 1 | 1), mid + 1, r, carry);
}
int main() {
  xxs(1e6);
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  scanf("%s", b + 1);
  memset(minn, 0x3f, sizeof(minn));
  for (int i = 0; i <= 1000000; i++) {
    zz[i].push_back({0, 0});
  }
  for (int i = 1; i <= n; i++) {
    while (a[i] > 1) {
      int t = minp[a[i]], dlt = 0;
      while (a[i] % t == 0) a[i] /= t, dlt++;
      if (b[i] == '/') dlt = -dlt;
      zz[t].push_back({i, dlt});
    }
  }
  for (int i = 0; i <= 1000000; i++) {
    if ((int(zz[i].size())) <= 1) continue;
    for (int j = 1; j <= (int(zz[i].size())) - 1; j++)
      zz[i][j].dlt += zz[i][j - 1].dlt;
    zz[i].push_back({n + 1, 0});
    stk[top = 0] = (int(zz[i].size())) - 1;
    for (int j = (int(zz[i].size())) - 2; j >= 0; j--) {
      while (top && zz[i][stk[top]].dlt >= zz[i][j].dlt) --top;
      update(1, 1, n, zz[i][j].pos + 1, min(n, zz[i][j + 1].pos),
             zz[i][stk[top]].pos - 1);
      stk[++top] = j;
    }
  }
  dfs(1, 1, n, n);
  print(ans, '\n');
  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("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("avx", "avx2")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 1000005;
struct node {
  int pos, dlt;
};
vector<node> zz[N];
int a[N];
char b[N];
int stk[N], top, n;
int minp[N];
void xxs(int n) {
  for (int i = 2; i <= n; i++) {
    for (int j = i; j <= n; j += i)
      if (!minp[j]) minp[j] = i;
  }
}
int minn[N << 2];
void update(int u, int l, int r, int ql, int qr, int lim) {
  if (ql <= l && r <= qr) {
    ckmin(minn[u], lim);
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid) update((u << 1), l, mid, ql, qr, lim);
  if (qr > mid) update((u << 1 | 1), mid + 1, r, ql, qr, lim);
}
long long ans = 0;
void dfs(int u, int l, int r, int carry) {
  ckmin(carry, minn[u]);
  if (l == r) {
    ans += carry - l + 1;
    return;
  }
  int mid = l + r >> 1;
  dfs((u << 1), l, mid, carry);
  dfs((u << 1 | 1), mid + 1, r, carry);
}
int main() {
  xxs(1e6);
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  scanf("%s", b + 1);
  memset(minn, 0x3f, sizeof(minn));
  for (int i = 0; i <= 1000000; i++) {
    zz[i].push_back({0, 0});
  }
  for (int i = 1; i <= n; i++) {
    while (a[i] > 1) {
      int t = minp[a[i]], dlt = 0;
      while (a[i] % t == 0) a[i] /= t, dlt++;
      if (b[i] == '/') dlt = -dlt;
      zz[t].push_back({i, dlt});
    }
  }
  for (int i = 0; i <= 1000000; i++) {
    if ((int(zz[i].size())) <= 1) continue;
    for (int j = 1; j <= (int(zz[i].size())) - 1; j++)
      zz[i][j].dlt += zz[i][j - 1].dlt;
    zz[i].push_back({n + 1, 0});
    stk[top = 0] = (int(zz[i].size())) - 1;
    for (int j = (int(zz[i].size())) - 2; j >= 0; j--) {
      while (top && zz[i][stk[top]].dlt >= zz[i][j].dlt) --top;
      update(1, 1, n, zz[i][j].pos + 1, min(n, zz[i][j + 1].pos),
             zz[i][stk[top]].pos - 1);
      stk[++top] = j;
    }
  }
  dfs(1, 1, n, n);
  print(ans, '\n');
  return 0;
}

```