Séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ et un entier $K$ sont donnés. Écrire un programme qui exécute les requêtes suivantes :

• l r : Afficher la longueur de la plus longue sous-suite contiguë vérifiant $l \le i \le j \le r$ et $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • Si une telle sous-suite n'existe pas, la longueur est $0$.

Entrée

La première ligne contient la longueur de la séquence $N$ $(1 \le N \le 100\,000)$ et $K$ $(2 \le K \le 1\,000\,000)$.

La deuxième ligne contient $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1\,000\,000\,000)$.

La troisième ligne contient le nombre de requêtes $M$ $(1 \le M \le 100\,000)$.

Les $M$ lignes suivantes contiennent chacune une requête $l, r$ $(1 \le l \le r \le n)$.

Sortie

Pour chaque requête, afficher la réponse sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

3
3