長さ $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)$ が含まれる。

2 行目には $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 1{,}000{,}000{,}000)$ が含まれる。

3 行目にはクエリの数 $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