Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$ oraz liczba całkowita $K$. Napisz program, który wykonuje następujące zapytania:

• l r: Wypisz długość najdłuższego spójnego podciągu spełniającego $l \le i \le j \le r$ oraz $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • Jeśli taki podciąg nie istnieje, długość wynosi $0$.

Wejście

Pierwszy wiersz zawiera długość ciągu $N$ $(1 \le N \le 100{,}000)$ oraz $K$ $(2 \le K \le 1{,}000{,}000)$.

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{,}000{,}000{,}000)$.

Trzeci wiersz zawiera liczbę zapytań $M$ $(1 \le M \le 100{,}000)$.

Kolejne $M$ wierszy zawiera po jednym zapytaniu $l, r$ $(1 \le l \le r \le n)$.

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

3
3