И снова проголодался Крот. Он нашел одну муравьиную колонию из n муравьев, выстроенных в ряд. У каждого муравья i (1 ≤ i ≤ n) есть сила si.
Чтобы разнообразить ужин, Крот организует что-то вроде «Голодных игр» для муравьев. Он выбирает два номера, l и r (1 ≤ l ≤ r ≤ n) и каждая пара муравьев с номерами от l до r (включительно) сражается. Когда сражаются два муравья i и j, муравей номер i получает одно боевое очко только в том случае, если si делит sj (также, муравей j получает одно боевое очко только в том случае, если sj делит si).
Когда все битвы остаются позади, Крот распределяет места. Муравей номер i, получивший vi боевых баллов, будет освобожден только если vi = r - l, или — иными словами — только если он получал по баллу в каждой битве, в которой он принимал участие. Затем Крот поедает остальных муравьев. Обратите внимание на то, что освобождёнными могут оказаться как много муравьев, так и нисколько.
Чтобы выбрать наилучший вариант, Крот дает вам t отрезков [li, ri] и спрашивает для каждого отрезка: сколько муравьев он съест, если эти муравьи будут биться?
Выходные данные
Выведите t строк. В i-й строке должно следовать количество муравьев из отрезка [li, ri], которые будут отданы на съедение Кроту.
Примечание
В первом тесте очки для каждого муравья такие: v = [4, 0, 2, 0, 2], так что муравей 1 освобождается. Крот съедает муравьев номер 2, 3, 4, 5.
Во втором тесте очки такие: v = [0, 2, 0, 2], ни один муравей не освобождается, Крот съедает их всех.
В третьем тесте очки такие: v = [2, 0, 2], освобождаются муравьи номер 3 и 5. Крот поедает только муравья номер 4.
В четвертом тесте очки такие: v = [0, 1], так что муравей номер 5 освобождается. Крот съедает муравья номер 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
|
4
4
1
1
|