F. Муравьиная колония
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

И снова проголодался Крот. Он нашел одну муравьиную колонию из 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] и спрашивает для каждого отрезка: сколько муравьев он съест, если эти муравьи будут биться?

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 105) — размер муравьиной колонии.

Во второй строке записано n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 109) — силы муравьев.

В третьей строке записано одно число t (1 ≤ t ≤ 105) — количество запросов.

В каждой из следующих t строк записано по два целых числа li и ri (1 ≤ li ≤ ri ≤ n), описывающих один запрос.

Выходные данные

Выведите t строк. В i-й строке должно следовать количество муравьев из отрезка [li, ri], которые будут отданы на съедение Кроту.

Примеры
Входные данные
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
Выходные данные
4
4
1
1
Примечание

В первом тесте очки для каждого муравья такие: 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.