Cho dãy $A_1, A_2, \ldots, A_N$ độ dài $N$ và một số nguyên $K$. Viết chương trình thực hiện các truy vấn sau:

• l r: In ra độ dài của dãy con liên tiếp dài nhất thỏa mãn $l \le i \le j \le r$ và $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • Nếu không có dãy con nào như vậy, độ dài là $0$.

Dữ liệu vào

Dòng đầu tiên chứa độ dài dãy $N$ $(1 \le N \le 100{.}000)$ và $K$ $(2 \le K \le 1{.}000{.}000)$.

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{.}000{.}000{.}000)$.

Dòng thứ ba chứa số lượng truy vấn $M$ $(1 \le M \le 100{.}000)$.

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn $l, r$ $(1 \le l \le r \le n)$.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
3