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!