创作乐曲

Problem Description

众所周知，坎格鲁斯普雷喜欢创作乐曲。 根据《袋鼠韵律法则》，一首乐曲应由一定量的音符组成，且音符的音高应为 $1 \sim m$ 的整数；一首乐曲被认为是“美妙动听”的，当且仅当这首乐曲相邻的音符的音高差的绝对值不超过 $k$ 。 现在，坎格鲁斯普雷创作了一首有 $n$ 个音符的乐曲，其中第 $i$ 个音符的音高为 $a_i$ 。这时候，数据结构带师袋鼠将军出现了，它对你提出了 $q$ 个询问，每个询问形如：对于第 $l_i$ 个音符到第 $r_i$ 个音符组成的子乐曲，至少删除多少个音符才能使这个子乐曲是“美妙动听”的。 虽然你很不情愿，但你还是接受了袋鼠将军的挑战，不然你就会被袋鼠将军当作怯战蜥蜴的。

Input

输入第一行一个整数 $T$ ，表示测试数据组数。 $( 1 \leq T \leq 10^3 )$ 对于每组测试数据，第一行三个整数 $n$ ， $m$ ， $k$。 $(1 \leq n \leq 10^5,1 \leq m,k \leq 10^{18})$ 第二行 $n$ 个整数 $a_i$ ，表示第 $i$ 个音符的音高。 $(1 \leq a_i \leq m)$ 第三行一个整数 $q$ ，表示接下来有 $q$ 个询问。 $(1 \leq q \leq 500)$ 接下来的 $q$ 行，每行两个整数 $l_i$ ，$r_i$ ，表示一次询问。 $(1 \leq l_i \leq r_i \leq n)$ 数据保证 $\sum n \leq 4 \times 10^5,\sum q \leq 2 \times 10^3$ 。

Output

对于每组测试数据的每个询问，输出一行一个整数，表示答案。每个询问的答案之间需换行，不同测试数据之间的答案也需换行。

Sample Input

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

Sample Output

2
1
1
0
0
2
3

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）