众所周知，坎格鲁斯普雷喜欢创作乐曲。

根据《袋鼠韵律法则》，一首乐曲应由一定量的音符组成，且音符的音高应为 $1\sim m$ 的整数；一首乐曲被认为是“美妙动听”的，当且仅当这首乐曲相邻的音符的音高差的绝对值不超过 $k$ 。

现在，坎格鲁斯普雷创作了一首有 $n$ 个音符的乐曲，其中第 $i$ 个音符的音高为 $a_i$ 。这时候，数据结构带师袋鼠将军出现了，它对你提出了 $q$ 个询问，每个询问形如：对于第 $l_i$ 个音符到第 $r_i$ 个音符组成的子乐曲，至少删除多少个音符才能使这个子乐曲是“美妙动听”的。

虽然你很不情愿，但你还是接受了袋鼠将军的挑战，不然你就会被袋鼠将军当作怯战蜥蜴的。

输入第一行一个整数 $T$ ，表示测试数据组数。 $(1≤T≤10^3 )$

对于每组测试数据，第一行三个整数 $n, m, k(1≤n≤10^5,1≤m,k≤10^{18} )$

第二行 $n$ 个整数 $a_i$ ，表示第 $i$ 个音符的音高。 $(1≤a_i ≤m)$

第三行一个整数 $q$ ，表示接下来有 $q$ 个询问。 $(1≤q≤500)$

接下来的 $q$ 行，每行两个整数 $l_i,r_i$ ，表示一次询问。 $(1≤l_i≤r_i ≤n)$

数据保证 $∑n≤4×10^5 ,∑q≤2×10^3$。

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