#include <bits/stdc++.h>
namespace cm {
class logger {
 private:
  std::ostream* out;
  std::string sep = "\x2c\x20";
  bool _assert_exit = true;
  std::string c_red = "\033[0;31m";
  std::string c_green = "\033[0;32m";
  std::string c_yellow = "\033[0;33m";
  std::string c_blue = "\033[0;34m";
  std::string c_magenta = "\033[0;35m";
  std::string c_cyan = "\033[0;36m";
  std::string c_red_bold = "\033[1;31m";
  std::string c_green_bold = "\033[1;32m";
  std::string c_yellow_bold = "\033[1;33m";
  std::string c_blue_bold = "\033[1;34m";
  std::string c_magenta_bold = "\033[1;35m";
  std::string c_cyan_bold = "\033[1;36m";
  std::string c_reset = "\033[0m";
  std::string get_color(std::string name) {
    if (name == "red") return c_red;
    if (name == "green") return c_green;
    if (name == "yellow") return c_yellow;
    if (name == "blue") return c_blue;
    if (name == "magenta") return c_magenta;
    if (name == "cyan") return c_cyan;
    if (name == "red bold") return c_red_bold;
    if (name == "green bold") return c_green_bold;
    if (name == "yellow bold") return c_yellow_bold;
    if (name == "blue bold") return c_blue_bold;
    if (name == "magenta bold") return c_magenta_bold;
    if (name == "cyan bold") return c_cyan_bold;
    if (name == "reset") return c_reset;
    return "";
  }

 public:
  logger(std::ostream& out) : out(&out) {}
  logger& set_ostream(std::ostream& out) {
    this->out = &out;
    return *this;
  }
  logger& set_sep(const std::string& sep) {
    this->sep = sep;
    return *this;
  }
  logger& assert_exit() {
    _assert_exit = true;
    return *this;
  }
  logger& assert_noexit() {
    _assert_exit = false;
    return *this;
  }
  logger& endl() {
    *out << std::endl;
    return *this;
  }
  logger& log() { return *this; }
  template <class Ta, class Tb, class... Tc>
  logger& log(const Ta& a, const Tb& b, Tc... c) {
    return log(a).log(sep).log(b, c...);
  }
  template <class Ta, typename = decltype(std::cout << std::declval<Ta>())>
  logger& log(const Ta& a) {
    *out << a;
    return *this;
  }
  template <class T, typename = decltype(std::declval<T>().begin()),
            typename = decltype(std::declval<T>().end()),
            typename = typename std::enable_if<!std::is_base_of<
                std::string, typename std::decay<T>::type>::value>::type,
            typename value_type = typename T::value_type>
  logger& log(const T& container) {
    log("{");
    for (auto it = container.begin(); it != container.end(); ++it) {
      if (it != container.begin()) log(sep);
      log(*it);
    }
    log("}");
    return *this;
  }
  template <class Ta, class Tb>
  logger& log(const std::pair<Ta, Tb>& x) {
    return log("(").log(x.first, x.second).log(")");
  }
  template <class... T>
  logger& log(const std::tuple<T...>&) {
    return log("<tuple>");
  }
  template <class T>
  logger& hint(const T& x, std::string color = "cyan") {
    color = get_color(color);
    return log(color).log(x).log("\x3a\x20").log(c_reset);
  }
  template <class... T>
  logger& operator()(T... value) {
    return log(value...).endl();
  }
  template <class... T>
  logger& _assert(const std::string& file, int line, const std::string& raw,
                  bool value, const std::string& info_str, T... info) {
    if (!value) {
      endl();
      hint(file, "magenta")
          .hint(line, "magenta")
          .log(c_yellow)
          .log("Assertion `")
          .log(c_yellow_bold)
          .log(raw)
          .log(c_yellow)
          .log("` failed")
          .log(c_reset)
          .endl();
      if (info_str != "") hint("detail", "magenta").hint(info_str)(info...);
      if (_assert_exit) exit(0);
    }
    return *this;
  }
};
namespace impl {
logger see_logger(std::cout);
}
}  // namespace cm
namespace cm {
template <class Type, size_t buf_size>
class buffer_reader {
 protected:
  FILE* src;
  Type* const buff;
  Type* buff_end;
  Type* buff_pos;
  void flush() {
    buff_end = buff + fread(buff, sizeof(Type), buf_size, src);
    buff_pos = buff;
    if (buff_end == buff) {
      *buff_end = '\0';
    }
  }

 public:
  buffer_reader(FILE* src) : src(src), buff(new Type[buf_size]) { flush(); }
  buffer_reader(const buffer_reader&) = delete;
  buffer_reader(buffer_reader&&) = delete;
  buffer_reader& operator=(const buffer_reader&) = delete;
  buffer_reader& operator=(buffer_reader&&) = delete;
  Type get() const { return *buff_pos; }
  Type next() {
    Type result = get();
    buff_pos++;
    if (buff_pos == buff_end) flush();
    return result;
  }
  ~buffer_reader() {
    fclose(src);
    delete[] buff;
  }
};
using optimal_reader = buffer_reader<char, 1 << 16>;
template <class BufferReader>
class scanner : protected BufferReader {
 private:
  using BufferReader::get;
  using BufferReader::next;
  inline bool is_ws(char c) { return c <= ' '; }
  inline bool is_cr(char c) { return c == '\n' || c == '\r'; }
  int get_sign() {
    while (!isdigit(get()) && get() != '-') next();
    if (get() == '-') return next(), -1;
    return 1;
  }

 public:
  scanner() = delete;
  using BufferReader::BufferReader;
  char next_char() {
    while (is_ws(get())) next();
    return next();
  }
  char* next_token(char* s) {
    while (is_ws(get())) next();
    while (!is_ws(get())) *s++ = next();
    *s = '\0';
    return s;
  }
  char* next_line(char* s) {
    while (is_ws(get())) next();
    while (!is_cr(get())) *s++ = next();
    *s = '\0';
    return s;
  }
  int next_int() {
    int sign = get_sign();
    int result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    return sign * result;
  }
  long long next_long() {
    int sign = get_sign();
    long long result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    return sign * result;
  }
  long long next_modint(long long mod) {
    get_sign();
    long long result = 0;
    while (isdigit(get())) result = (result * 10 + (next() - '0')) % mod;
    return result;
  }
  double next_double() {
    int sign = get_sign();
    double result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    if (get() == '.') {
      next();
      double cur_ep = 0.1;
      while (isdigit(get())) result += cur_ep * (next() - '0'), cur_ep *= 0.1;
    }
    return sign * result;
  }
};
}  // namespace cm
namespace cm {
template <class T>
inline bool check_min(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool check_max(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
struct once_t {
  bool once = true;
  bool operator()() { return once ? (once = false, true) : false; }
};
}  // namespace cm
using cm::check_max;
using cm::check_min;
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B> operator+(
    const std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  return std::make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B> operator-(
    const std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  return std::make_pair(lhs.first - rhs.first, lhs.second - rhs.second);
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B>& operator+=(
    std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  lhs.first += rhs.first;
  lhs.second += rhs.second;
  return lhs;
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B>& operator-=(
    std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  lhs.first -= rhs.first;
  lhs.second -= rhs.second;
  return lhs;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, const std::vector<T>& b) {
  a.insert(a.end(), b.begin(), b.end());
  return a;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, const T& b) {
  a.insert(a.end(), b);
  return a;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, T&& b) {
  a.insert(a.end(), std::forward<T>(b));
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, const std::vector<T>& b) {
  a += b;
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, T& b) {
  a += b;
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, T&& b) {
  a += std::forward<T>(b);
  return a;
}
cm::scanner<cm::optimal_reader> sc(stdin);
constexpr int N = 1000005;
int prime[N];
void init_prime() {
  for (int i = 2; i < N; i++)
    if (prime[i] == 0) {
      for (int j = i; j < N; j += i) prime[j] = i;
    }
}
std::vector<int> pos[N];
int a[N], l[N], n;
void insert(int p, int x) {
  l[p] = p;
  while (x > 1) {
    pos[prime[x]].push_back(p);
    ;
    x /= prime[x];
  }
}
void erase(int p, int x) {
  l[p] = p;
  while (x > 1) {
    if (pos[prime[x]].empty())
      l[p] = 0;
    else {
      check_min(l[p], pos[prime[x]].back());
      pos[prime[x]].pop_back();
    };
    x /= prime[x];
  }
}
int main() {
  init_prime();
  n = sc.next_int();
  for (int i = 1; i <= n; i++) a[i] = sc.next_int();
  for (int i = 1; i <= n; i++) {
    char ty = sc.next_char();
    if (ty == '*')
      insert(i, a[i]);
    else
      erase(i, a[i]);
  }
  std::vector<int> st;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    st.push_back(i);
    while (!st.empty() && st.back() > l[i]) st.pop_back();
    ;
    ans += st.size();
  }
  std::cout << ans << std::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>
namespace cm {
class logger {
 private:
  std::ostream* out;
  std::string sep = "\x2c\x20";
  bool _assert_exit = true;
  std::string c_red = "\033[0;31m";
  std::string c_green = "\033[0;32m";
  std::string c_yellow = "\033[0;33m";
  std::string c_blue = "\033[0;34m";
  std::string c_magenta = "\033[0;35m";
  std::string c_cyan = "\033[0;36m";
  std::string c_red_bold = "\033[1;31m";
  std::string c_green_bold = "\033[1;32m";
  std::string c_yellow_bold = "\033[1;33m";
  std::string c_blue_bold = "\033[1;34m";
  std::string c_magenta_bold = "\033[1;35m";
  std::string c_cyan_bold = "\033[1;36m";
  std::string c_reset = "\033[0m";
  std::string get_color(std::string name) {
    if (name == "red") return c_red;
    if (name == "green") return c_green;
    if (name == "yellow") return c_yellow;
    if (name == "blue") return c_blue;
    if (name == "magenta") return c_magenta;
    if (name == "cyan") return c_cyan;
    if (name == "red bold") return c_red_bold;
    if (name == "green bold") return c_green_bold;
    if (name == "yellow bold") return c_yellow_bold;
    if (name == "blue bold") return c_blue_bold;
    if (name == "magenta bold") return c_magenta_bold;
    if (name == "cyan bold") return c_cyan_bold;
    if (name == "reset") return c_reset;
    return "";
  }

 public:
  logger(std::ostream& out) : out(&out) {}
  logger& set_ostream(std::ostream& out) {
    this->out = &out;
    return *this;
  }
  logger& set_sep(const std::string& sep) {
    this->sep = sep;
    return *this;
  }
  logger& assert_exit() {
    _assert_exit = true;
    return *this;
  }
  logger& assert_noexit() {
    _assert_exit = false;
    return *this;
  }
  logger& endl() {
    *out << std::endl;
    return *this;
  }
  logger& log() { return *this; }
  template <class Ta, class Tb, class... Tc>
  logger& log(const Ta& a, const Tb& b, Tc... c) {
    return log(a).log(sep).log(b, c...);
  }
  template <class Ta, typename = decltype(std::cout << std::declval<Ta>())>
  logger& log(const Ta& a) {
    *out << a;
    return *this;
  }
  template <class T, typename = decltype(std::declval<T>().begin()),
            typename = decltype(std::declval<T>().end()),
            typename = typename std::enable_if<!std::is_base_of<
                std::string, typename std::decay<T>::type>::value>::type,
            typename value_type = typename T::value_type>
  logger& log(const T& container) {
    log("{");
    for (auto it = container.begin(); it != container.end(); ++it) {
      if (it != container.begin()) log(sep);
      log(*it);
    }
    log("}");
    return *this;
  }
  template <class Ta, class Tb>
  logger& log(const std::pair<Ta, Tb>& x) {
    return log("(").log(x.first, x.second).log(")");
  }
  template <class... T>
  logger& log(const std::tuple<T...>&) {
    return log("<tuple>");
  }
  template <class T>
  logger& hint(const T& x, std::string color = "cyan") {
    color = get_color(color);
    return log(color).log(x).log("\x3a\x20").log(c_reset);
  }
  template <class... T>
  logger& operator()(T... value) {
    return log(value...).endl();
  }
  template <class... T>
  logger& _assert(const std::string& file, int line, const std::string& raw,
                  bool value, const std::string& info_str, T... info) {
    if (!value) {
      endl();
      hint(file, "magenta")
          .hint(line, "magenta")
          .log(c_yellow)
          .log("Assertion `")
          .log(c_yellow_bold)
          .log(raw)
          .log(c_yellow)
          .log("` failed")
          .log(c_reset)
          .endl();
      if (info_str != "") hint("detail", "magenta").hint(info_str)(info...);
      if (_assert_exit) exit(0);
    }
    return *this;
  }
};
namespace impl {
logger see_logger(std::cout);
}
}  // namespace cm
namespace cm {
template <class Type, size_t buf_size>
class buffer_reader {
 protected:
  FILE* src;
  Type* const buff;
  Type* buff_end;
  Type* buff_pos;
  void flush() {
    buff_end = buff + fread(buff, sizeof(Type), buf_size, src);
    buff_pos = buff;
    if (buff_end == buff) {
      *buff_end = '\0';
    }
  }

 public:
  buffer_reader(FILE* src) : src(src), buff(new Type[buf_size]) { flush(); }
  buffer_reader(const buffer_reader&) = delete;
  buffer_reader(buffer_reader&&) = delete;
  buffer_reader& operator=(const buffer_reader&) = delete;
  buffer_reader& operator=(buffer_reader&&) = delete;
  Type get() const { return *buff_pos; }
  Type next() {
    Type result = get();
    buff_pos++;
    if (buff_pos == buff_end) flush();
    return result;
  }
  ~buffer_reader() {
    fclose(src);
    delete[] buff;
  }
};
using optimal_reader = buffer_reader<char, 1 << 16>;
template <class BufferReader>
class scanner : protected BufferReader {
 private:
  using BufferReader::get;
  using BufferReader::next;
  inline bool is_ws(char c) { return c <= ' '; }
  inline bool is_cr(char c) { return c == '\n' || c == '\r'; }
  int get_sign() {
    while (!isdigit(get()) && get() != '-') next();
    if (get() == '-') return next(), -1;
    return 1;
  }

 public:
  scanner() = delete;
  using BufferReader::BufferReader;
  char next_char() {
    while (is_ws(get())) next();
    return next();
  }
  char* next_token(char* s) {
    while (is_ws(get())) next();
    while (!is_ws(get())) *s++ = next();
    *s = '\0';
    return s;
  }
  char* next_line(char* s) {
    while (is_ws(get())) next();
    while (!is_cr(get())) *s++ = next();
    *s = '\0';
    return s;
  }
  int next_int() {
    int sign = get_sign();
    int result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    return sign * result;
  }
  long long next_long() {
    int sign = get_sign();
    long long result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    return sign * result;
  }
  long long next_modint(long long mod) {
    get_sign();
    long long result = 0;
    while (isdigit(get())) result = (result * 10 + (next() - '0')) % mod;
    return result;
  }
  double next_double() {
    int sign = get_sign();
    double result = 0;
    while (isdigit(get())) result = result * 10 + (next() - '0');
    if (get() == '.') {
      next();
      double cur_ep = 0.1;
      while (isdigit(get())) result += cur_ep * (next() - '0'), cur_ep *= 0.1;
    }
    return sign * result;
  }
};
}  // namespace cm
namespace cm {
template <class T>
inline bool check_min(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool check_max(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
struct once_t {
  bool once = true;
  bool operator()() { return once ? (once = false, true) : false; }
};
}  // namespace cm
using cm::check_max;
using cm::check_min;
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B> operator+(
    const std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  return std::make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B> operator-(
    const std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  return std::make_pair(lhs.first - rhs.first, lhs.second - rhs.second);
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B>& operator+=(
    std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  lhs.first += rhs.first;
  lhs.second += rhs.second;
  return lhs;
}
template <class A, class B>
inline __attribute__((always_inline)) std::pair<A, B>& operator-=(
    std::pair<A, B>& lhs, const std::pair<A, B>& rhs) {
  lhs.first -= rhs.first;
  lhs.second -= rhs.second;
  return lhs;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, const std::vector<T>& b) {
  a.insert(a.end(), b.begin(), b.end());
  return a;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, const T& b) {
  a.insert(a.end(), b);
  return a;
}
template <class T>
std::vector<T>& operator+=(std::vector<T>& a, T&& b) {
  a.insert(a.end(), std::forward<T>(b));
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, const std::vector<T>& b) {
  a += b;
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, T& b) {
  a += b;
  return a;
}
template <class T>
std::vector<T> operator+(std::vector<T> a, T&& b) {
  a += std::forward<T>(b);
  return a;
}
cm::scanner<cm::optimal_reader> sc(stdin);
constexpr int N = 1000005;
int prime[N];
void init_prime() {
  for (int i = 2; i < N; i++)
    if (prime[i] == 0) {
      for (int j = i; j < N; j += i) prime[j] = i;
    }
}
std::vector<int> pos[N];
int a[N], l[N], n;
void insert(int p, int x) {
  l[p] = p;
  while (x > 1) {
    pos[prime[x]].push_back(p);
    ;
    x /= prime[x];
  }
}
void erase(int p, int x) {
  l[p] = p;
  while (x > 1) {
    if (pos[prime[x]].empty())
      l[p] = 0;
    else {
      check_min(l[p], pos[prime[x]].back());
      pos[prime[x]].pop_back();
    };
    x /= prime[x];
  }
}
int main() {
  init_prime();
  n = sc.next_int();
  for (int i = 1; i <= n; i++) a[i] = sc.next_int();
  for (int i = 1; i <= n; i++) {
    char ty = sc.next_char();
    if (ty == '*')
      insert(i, a[i]);
    else
      erase(i, a[i]);
  }
  std::vector<int> st;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    st.push_back(i);
    while (!st.empty() && st.back() > l[i]) st.pop_back();
    ;
    ans += st.size();
  }
  std::cout << ans << std::endl;
  return 0;
}

```