Кузя начал ходить в школу. На уроке математики ему дали домашнее задание. Для этого задания ему выдали массив натуральных чисел \(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\)). Так как у него явно нет ни времени, ни желания проводить вычисления для всех вариантов, он попросил вас написать программу, чтобы узнать это количество!