Sequence $A_1, A_2, \ldots, A_N$ of length $N$ and an integer $K$ are given. Write a program that executes the following queries:

• l r: Output the length of the longest contiguous subsequence satisfying $l \le i \le j \le r$ and $(A_i + A_{i+1} + \ldots + A_j) \bmod K = 0$.
  • If no such subsequence exists, the length is $0$.

Input

The first line contains the length of the sequence $N$ $(1 \le N \le 100{,}000)$ and $K$ $(2 \le K \le 1{,}000{,}000)$.

The second line contains $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{,}000{,}000{,}000)$.

The third line contains the number of queries $M$ $(1 \le M \le 100{,}000)$.

The next $M$ lines each contain a query $l, r$ $(1 \le l \le r \le n)$.

Output

For each query, output the answer on a separate line.

Examples

Input 1

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

Output 1

3
3