Description

A找B做游戏，B提议做一个奇怪的游戏，输的人需要请对方吃一顿饭，规则如下：给定一个数字N，以及N个数字Ai；现在有Q个询问，每次询问用两个数字L，R来表示，表示要求AL，AL+1，……AR-1,AR之中，能够被X整除的有多少个？ 但是A的智商太低，并且口袋里面没有钱。让你写个程序帮助他。

Input Format

第1行2个数字，表示N和X。

第2行N个数字，表示A1，A2……AN。 第3行1个数字，表示Q。 第4到Q+4-1行，每行有2个数字，分别表示每次询问中的L和R。

N的范围是【1..10^6】,1<=L,R<=N。

Output Format

输出一共有Q行。 每一行表示对于AL，AL+1，……AR-1,AR之中，能够被X整除的个数。

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

1
3
0
3