给你一个长度为 $N$ 的数列 $num\{\}$ 和一个固定的常数 $k$ , 一共有 $M$ 个询问 ,
每个询问查询 :

$$\sum\limits_{l \leq i,j \leq r} [\ num_i \ \text{mod}\ num_j=k \ ]$$

第一行三个正整数 $N,M,K$ , 意义如上。

第二行 $N$ 个正整数 代表 $num\{\}$。

以下 $M$ 行每行两个正整数 $l,r$。

一共 $M$ 行 , 每行一个非负整数代表答案。

时间限制 : $0.5\text s$ , 空间限制 : $400 \text M$。

$\max num_i \leq N$。

数据	$N,M$	$k$
$1$	$10$	$k \leq 10$
$2$	$10^2$	$k \leq 2\times 10$
$3$	$10^4$	$10^2 \leq k \leq 2 \times 10^2$
$4$	$10^4$	$10^2 \leq k \leq 2 \times 10^2$
$5$	$10^4$	$10^2 \leq k \leq 2 \times 10^2$
$6$	$5 \times 10^4$	$10^2 \leq k \leq 2 \times 10^2$
$7$	$5 \times 10^4$	$10^2 \leq k \leq 2 \times 10^2$
$8$	$5 \times 10^4$	$10^2 \leq k \leq 2 \times 10^2$
$9$	$5 \times 10^4$	$5 \times 10^2 \leq k \leq 2 \times 10^3$
$10$	$5 \times 10^4$	$5 \times 10^3 \leq k \leq 2 \times 10^4$