Se da una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$ y un entero $K$. Escribe un programa que ejecute las siguientes consultas:

• l r: Imprime la longitud de la subsecuencia contigua más larga que satisface $l \le i \le j \le r$ y $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • Si no existe tal subsecuencia, la longitud es $0$.

Entrada

La primera línea contiene la longitud de la secuencia $N$ $(1 \le N \le 100{,}000)$ y $K$ $(2 \le K \le 1{,}000{,}000)$.

La segunda línea contiene $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{,}000{,}000{,}000)$.

La tercera línea contiene el número de consultas $M$ $(1 \le M \le 100{,}000)$.

Las siguientes $M$ líneas contienen cada una una consulta $l, r$ $(1 \le l \le r \le n)$.

Salida

Para cada consulta, imprime la respuesta en una línea separada.

Ejemplos

Entrada 1

5 10
2 3 5 2 3
2
1 3
2 4

Salida 1

3
3