CF1582G.Kuzya and Homework

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 \le l \le r \le 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=\frac{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 \le l \le r \le 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!

库济亚开始上学了。他得到了一份数学作业，其中给了一个长度为 $n$ 的数组 $a$ 和一个长度为 $n$ 的符号数组 $b$，其中 $b$ 仅由字符 * 和 / 组成。

我们定义区间 $[l; r]$（$1 \le l \le r \le n$）的计算路径如下：

• 初始令 $x = 1$；
• 对每个 $i$ 从 $l$ 到 $r$ 依次执行：若 $b_i =\,$*，则令 $x = x \times a_i$；若 $b_i =\,$/，则令 $x = \dfrac{x}{a_i}$。
• 将该过程中每一步得到的 $x$ 值按顺序组成的列表称为区间 $[l; r]$ 的计算路径（其长度恰好为 $r - l + 1$）。

例如，设 $a=[7,\ 12,\ 3,\ 5,\ 4,\ 10,\ 9]$，$b=[/,\ *,\ /,\ /,\ /,\ *,\ *]$，且 $l=2$，$r=6$，则该区间的计算路径为 $[12,\ 4,\ 0.8,\ 0.2,\ 2]$。

若一个区间 $[l;r]$ 的计算路径中所有数值均为整数，则称该区间为简单区间。

库济亚需要找出所有满足 $1 \le l \le r \le n$ 的简单区间 $[l;r]$ 的个数。显然，他既没时间也没兴趣手动枚举并验证每一个可能的区间，因此请你编写一个程序来求出这个数目！

The first line contains a single integer $n$ ($2 \le n \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).

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

第一行包含一个整数 $n$（$2 \le n \le 10^6$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）。

第三行包含 $n$ 个无空格分隔的符号——数组 $b_1, b_2, \ldots, b_n$（对每个 $1 \le i \le n$，有 $b_i =$ '/' 或 $b_i =$ '*'）。

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

输出一个整数——简单区间 $[l;r]$ 的数量。