Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$ и целое число $K$. Напишите программу, которая выполняет следующие запросы:

• l r: Выведите длину самого длинного непрерывного подотрезка, удовлетворяющего условию $l \le i \le j \le r$ и $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • Если такого подотрезка не существует, длина равна $0$.

Входные данные

Первая строка содержит длину последовательности $N$ $(1 \le N \le 100{,}000)$ и $K$ $(2 \le K \le 1{,}000{,}000)$.

Вторая строка содержит $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{,}000{,}000{,}000)$.

Третья строка содержит количество запросов $M$ $(1 \le M \le 100{,}000)$.

Следующие $M$ строк содержат по одному запросу $l, r$ $(1 \le l \le r \le n)$.

Выходные данные

Для каждого запроса выведите ответ на отдельной строке.

Примеры

Входные данные 1

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

Выходные данные 1

3
3