序列
题号：NC14690
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

读入一个长度为n的整数数列a1,a2,…,an，以及一个整数K。
q组询问。
每组询问包含一个二元组(l, r), 其中1≤l≤r≤ n,
求所有满足以下条件的二元组(l2, r2)的数目:
1: 1≤l≤l2≤r2≤r≤n,
2: 是k的倍数。

输入描述:

第一行一个整数T，表示有T组数据。
对于每组数据，
第一行输入3个整数, n, q, k，
接下来一行输入n个整数，a1,a2,…,an，
接下来q行，每行输入2个整数 l, r

输出描述:

对于每一个询问，输出满足条件的二元组(l2,r2)的数目。
示例1

输入

复制 
1
5 2 4
4 1 4 8 8
2 2 
2 4

输出

复制 
0
3

说明

当(l, r)为(2, 4)时，
有
(l2,r2)=(3,4),a3+a4=12,是4的倍数
(l2,r2)=(3,3),a3=4,是4的倍数
(l2,r2)=(4,4),a4=8,是4的倍数

备注:

1≤ n,q ≤5×104,
1≤ l ≤ r ≤n,
1≤ ai, k ≤109,
保证∑n ≤6×104,∑q ≤6×104