长度为 $N$ 的序列 $A_1, A_2, \ldots, A_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