众所周知，坎格鲁斯普雷喜欢创作乐曲。
根据《袋鼠韵律法则》，一首乐曲应由一定量的音符组成，且音符的音高应为 1∼m 的整数；一首乐曲被认为是“美妙动听”的，当且仅当这首乐曲相邻的音符的音高差的绝对值不超过 k 。
现在，坎格鲁斯普雷创作了一首有 n个音符的乐曲，其中第 i 个音符的音高为 ai。这时候，数据结构带师袋鼠将军出现了，它对你提出了 qq 个询问，每个询问形如：对于第 li个音符到第 ri 个音符组成的子乐曲，至少删除多少个音符才能使这个子乐曲是“美妙动听”的。
虽然你很不情愿，但你还是接受了袋鼠将军的挑战，不然你就会被袋鼠将军当作怯战蜥蜴的。
输入第一行一个整数 T ，表示测试数据组数。 (1≤T≤103)
对于每组测试数据，第一行三个整数 n ， m ， k。(1≤n≤105,1≤m,k≤1018)
第二行 n 个整数 ai ，表示第 ii 个音符的音高。 (1≤ai≤m)
第三行一个整数 q ，表示接下来有 q 个询问。 (1≤q≤500)
接下来的 q 行，每行两个整数 li ，ri ，表示一次询问。(1≤li≤ri≤n)
数据保证 ∑n≤4×105,∑q≤2×103 。
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 62
1
1
0
0
2
3