Alex tiene una secuencia de ~n~ enteros ~a_1 ,a_2 ,...,a_n~ y ~q~ preguntas ~x_1 ,x_2 ,...,x_q~ . La respuesta de la i-ésima pregunta es la cantidad de pares ~(l,r)~ tal que ~1 \leq l \leq r \leq n~ y ~gcd(a_i ,a_{i+1} ,...,a_r ) = x_i~ .

Ayuda a Alex a responder todas sus preguntas.

Entrada

La primera línea de la entrada contiene al entero ~n~ (~1 \leq n \leq 10^5~ ).

La segunda línea de la entrada contiene los elementos de la secuencia ~a_1 , a_2 ,..., a_n~ , tal que ~1 \leq a_i \leq 10^9~, separados por un espacio.

La tercera línea de la entrada contiene al entero \(q (1 \leq q \leq 3 · 10^5 )\).

Las siguientes ~q~ líneas de la entrada contienen una pregunta ~x_i (1 \leq x_i \leq 10^9)~.

Salida

Imprima ~q~ líneas, la respuesta a cada pregunta, una por línea.

Eemplo #1 de Entrada Salida

3
2 6 3
5
1
2
3
4
6

Eemplo #1 de Salida

1
2
2
0
1

Eemplo #2 de Entrada

7
10 20 3 15 1000 60 16
10
1
2
3
4
5 
6
10
20
60
1000

Eemplo #2 de Salida

14
0
2
2
2
0
2
2
1
1