Zeus 正在分析战斗回放，以了解对手的攻击模式。对手拥有一项特殊能力：如果他们在 $z$ 的时间范围内对目标发动了三次攻击，他们的第三次攻击就会变成一次强力的强化攻击。

为了战胜对手，Zeus 不应该让对手触发他们的强化攻击。设 $Y = \{y_1, y_2, \dots, y_m\}$ 是由 $m$ 个时间戳组成的多重集，其中每个 $y_i$ 表示对手攻击命中的时间。如果对于任意三个时间戳 $\{y_i, y_j, y_k\}$（满足 $1 \le i < j < k \le m$），均满足 $\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) > z$，则称 $Y$ 是安全的（safe），其中 $z$ 是作为输入给出的时间范围长度。

Zeus 拥有一个包含 $n$ 个时间戳的日志 $x_1, x_2, \dots, x_n$，表示对手攻击命中的时间。这些时间戳按非降序排列。换句话说，对于所有 $1 \le i < n$，满足 $x_i \le x_{i+1}$。

Zeus 有 $q$ 个感兴趣的区间，每个区间由两个整数 $1 \le l \le r \le n$ 表示。对于每个区间，Zeus 想要找到在 $[x_l, x_{l+1}, \dots, x_r]$ 中他最多可以放行多少次攻击：换句话说，Zeus 想要找到多重集 $\{x_l, x_{l+1}, \dots, x_r\}$ 的一个最大大小的子集，使得该子集是安全的。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 20\,000$）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $z$（$1 \le n \le 250\,000$，$1 \le z \le 10^9$）。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \le x_i \le 10^9$）—— 对手攻击的时间戳。保证数组 $x$ 已排序，即对于所有 $1 \le i < n$，满足 $x_i \le x_{i+1}$。

第三行包含一个整数 $q$（$1 \le q \le 250\,000$）。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）—— 区间的端点。

保证所有测试用例中 $n$ 的总和不超过 $250\,000$。

保证所有测试用例中 $q$ 的总和不超过 $250\,000$。

输出格式

对于每个 $q$ 询问，输出一个整数 —— 在给定区间内，攻击时间戳的安全子集的最大大小。

样例

输入样例 1

3
6 10
1 5 7 8 11 12
6
1 6
1 5
2 6
1 4
2 5
3 6
6 1
1 1 1 3 3 3
2
3 3
1 6
12 15
4 5 15 24 27 32 36 39 40 46 48 48
20
1 12
1 11
6 10
1 8
8 12
11 12
2 9
3 8
7 8
7 10
4 8
9 12
9 10
2 12
1 5
3 12
4 8
3 7
7 12
10 11

输出样例 1

3
2
2
2
2
2
1
4
6
6
2
4
2
2
5
3
2
2
2
2
2
6
4
5
2
3
2
2

说明

在第一个测试用例的第一个询问中，我们考虑时间戳 $\{1, 5, 7, 8, 11, 12\}$，其中 $z = 10$。子集 $\{1, 5, 12\}$ 是安全的，因为其唯一的三元组满足 $12 - 1 = 11 > 10$。无法构造一个大小为 $4$ 的安全子集，因此该询问的答案为 $3$。

在第一个测试用例的第二个询问中，我们考虑时间戳 $\{1\}$，其中 $z = 1$。整个集合 $\{1\}$ 是安全的，因为不存在三元组。因此该询问的答案为 $1$。

在第二个测试用例的第二个询问中，我们考虑时间戳 $\{1, 1, 1, 3, 3, 3\}$，其中 $z = 1$。子集 $S = \{1, 1, 3, 3\}$ 是安全的，因为：

• 对于三元组 $(i, j, k) = (1, 2, 3)$，$\max(1, 1, 3) - \min(1, 1, 3) = 2 > 1$。
• 对于三元组 $(i, j, k) = (1, 2, 4)$，$\max(1, 1, 3) - \min(1, 1, 3) = 2 > 1$。
• 对于三元组 $(i, j, k) = (1, 3, 4)$，$\max(1, 3, 3) - \min(1, 3, 3) = 2 > 1$。
• 对于三元组 $(i, j, k) = (2, 3, 4)$，$\max(1, 3, 3) - \min(1, 3, 3) = 2 > 1$。

无法构造一个大小为 $5$ 的安全子集，因此该询问的答案为 $4$。