Description

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

Input

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

Output

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

Samples

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

2 
1 
1
0
0
2
3