Iris 刚刚在数学课上学会了乘法。然而,由于她的大脑无法承受太复杂的计算,她无法将两个乘积大于$$$k$$$的整数相乘。不然她的脑子可能会爆炸!
她的老师每天都会给她布置一项艰巨的任务,作为她每天的暑假作业。现在给她一个由 $$$n$$$ 元素组成的数组 $$$a$$$,她需要计算每两个相邻元素的乘积(即 $$$a_1 \cdot a_2$$$、$$$a_2 \cdot a_3$$$ 等)。 Iris 希望她的大脑安全地工作,为了做到这一点,她希望修改数组 $$$a$$$,使得 $$$a_i \cdot a_{i + 1} \leq k$$$ 对于每个 $$$1 \leq i < n$$$ 成立。她可以执行两种类型的操作:
1. 她可以以任意方式重新排列数组 $$$a$$$ 的元素。
2. 她可以选择数组 $$$a$$$ 中的任意元素,并将其值更改为 $$$1$$$ 到 $$$k$$$ 之间的任意整数。
Iris 希望最大限度地减少她使用的 $$$2$$$ 类型的操作数量。
然而,这完全不是暑假的结束!暑假持续 $$$q$$$ 天,在第 $$$i$$$ 天,Iris 被要求解决子数组 $$$b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}$$$ 的数学作业。帮助 Iris 并告诉她每天需要执行的最少 $$$2$$$ 类型操作。请注意,每天的操作都是独立的,即数组 $$$b$$$ 不会更改。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$q$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$, $$$1 \leq k \leq 10^6$$$) — 数组的长度$$$b$$$、天数以及乘法计算的上限。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq k$$$) — 数组 $$$b$$$ 的元素。
接下来是 $$$q$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — 第 $$$i$$$ 天的子数组的边界。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$q$$$总和不超过$$$10^5$$$。
输出
对于每个测试,输出一行包含 $$$q$$$ 整数 — 每天所需的 $$$2$$$ 类型的最小操作数。
示例
输入 #1
5 3 1 1 1 1 1 1 3 3 2 10 1 10 9 1 3 2 3 5 4 2 2 2 2 2 2 1 2 2 4 2 5 1 5 6 5 10 3 2 5 10 10 1 1 4 3 6 1 6 2 5 5 6 10 10 10 10 9 8 7 6 5 4 3 2 1 1 10 1 9 1 8 1 7 2 10 3 10 4 10 5 10 3 9 6 8
输出 #1
0 0 1 1 1 2 2 1 1 1 1 0 3 3 4 3 2 2 1 1 2 1
注意
在第一个测试用例中,由于 Iris 总是可以将 $$$1$$$ 和 $$$1$$$ 相乘,因此不需要任何操作,所以答案是 $$$0$$$。
在第二个测试用例中,第一天的作业是$$$[1, 10, 9]$$$。 Iris 可以重新排列其元素以获得 $$$[9, 1, 10]$$$,因此不需要 $$$2$$$ 类型的操作。第二天的作业是$$$[10, 9]$$$,她可以改变一个元素得到数组$$$[1, 9]$$$,所以需要一次$$$2$$$类型的操作。