Кузя начал ходить в школу. На уроке математики ему дали домашнее задание. Для этого задания ему выдали массив натуральных чисел $$$a$$$ длины $$$n$$$ и массив символов $$$b$$$ длины $$$n$$$, состоящий только из символов '*' или '/'.

Давайте определим траекторию вычислений для отрезка $$$[l; r]$$$ ($$$1 \le l \le r \le n$$$) следующим образом:

• Пусть изначально $$$x=1$$$. Для всех $$$i$$$ от $$$l$$$ до $$$r$$$ последовательно выполним следующее: если $$$b_i=$$$ '*', $$$x=x*a_i$$$, а если $$$b_i=$$$ '/', то $$$x=\frac{x}{a_i}$$$. Траекторией вычисления для отрезка $$$[l; r]$$$ назовем список всех $$$x$$$, которые были получены в процессе вычислений (их будет ровно $$$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]$$$ простым, если траектория вычислений для него содержит только целые числа.

Кузе нужно посчитать количество простых отрезков $$$[l;r]$$$ ($$$1 \le l \le r \le n$$$). Так как у него явно нет ни времени, ни желания проводить вычисления для всех вариантов, он попросил вас написать программу, чтобы узнать это количество!