Контролёр проверяет партии изделий. У каждого изделия есть числовой код. Изделие считается подходящим, если его код кратен заданному числу d.

Дана последовательность кодов n изделий и q запросов. Каждый запрос задаёт границы партии l, r и требует определить, сколько изделий на отрезке от l до r включительно имеют код, кратный d.

Требуется для каждого запроса вывести количество подходящих изделий.

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

В первой строке заданы два целых числа n и d — количество изделий и заданный делитель.

Во второй строке содержатся n целых чисел a_i — коды изделий.

В третьей строке задано целое число q — количество запросов.

В следующих q строках записаны пары целых чисел l и r — границы партии.

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

Для каждого запроса выведите одно целое число — количество изделий с кодом, кратным d, на отрезке [l, r].

Ограничения

• 1 <= n <= 2 * 10^5
• 1 <= d <= 10^9
• 1 <= a_i <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= l <= r <= n

Примеры

Пример 1

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

6 3
3 1 6 4 9 2
2
1 6
2 4

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

3
1

Пояснение

Кратные 3: на [1,6] это 3,6,9 — три; на [2,4] это 6 — одно.

Пример 2

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

1 1
779
2
1 1
1 1

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

1
1