Colônia de Formigas
Mole é um tamanduá, e está com muita fome. Ele encontrou uma colônia de formigas, composta por $$n$$ formigas, ordenadas em sequência. Cada formiga $$i$$ $$(1 \leq i \leq n)$$ tem uma força $$s_i$$.
Para tornar seu jantar mais interessante, Mole organiza uma versão dos «Jogos Vorazes» para as formigas. Ele escolhe dois números $$l$$ e $$r$$ $$(1 \leq l \leq r \leq n)$$ e cada par de formigas com índices entre $$l$$ e $$r$$ (inclusive) lutará. Quando duas formigas $$i$$ e $$j$$ lutam, a formiga $$i$$ obtém um ponto de batalha apenas se $$s_i$$ divide $$s_j$$ (também, formiga $$j$$ obtém um ponto de batalha somente se $$s_j$$ divide $$s_i$$).
Depois que todas as lutas forem concluídas, Mole faz o ranking. Uma formiga, com $$v_i$$ pontos de batalha obtidos, será liberada somente se $$v_i = r – l$$, ou seja, somente se tiver um ponto em todas as lutas que participou. Depois disso, Mole come o resto das formigas. Observe que pode haver muitas formigas liberadas ou mesmo nenhuma.
Entrada
A primeira linha contém um número inteiro $$n$$ ($$1 \leq n \leq 10^5$$), o tamanho da colônia de formigas.
A segunda linha contém $$n$$ números inteiros $$s_1$$, $$s_2$$, …, $$s_n$$ ($$1 \leq s_i \leq 10^9$$), as forças das formigas.
A terceira linha contém um número inteiro $$t$$ ($$1 \leq t \leq 10^5$$), o número de casos de teste.
Cada uma das próximas $$t$$ linhas contém dois números inteiros $$l_i$$ e $$r_i$$ ($$1 \leq l_i \leq r_i \leq n$$), descrevendo uma consulta.
Saída
Imprima $$t$$ linhas. A $$i$$-ésima linha contém o número de formigas que Mole come no segmento [$$l_i, r_i$$].
Exemplos
| ENTRADA | SAÍDA |
| 5 1 3 2 4 2 4 1 5 2 5 3 5 4 5 |
4 4 1 1 |
Enviar solução: codeforces