← 返回题目列表

Codeforces · 1066/A

A. Vova 和火车

中文机器翻译题面 查看原题

Vova 计划乘火车去参加会议。最初,火车位于点$$$1$$$,路径的目的地点是点$$$L$$$。火车的速度是每分钟 $$$1$$$ 长度单位(即第一分钟火车位于 $$$1$$$ 点,第二分钟位于 $$$2$$$ 点,依此类推)。

路上有灯笼。它们被放置在坐标可被 $$$v$$$ 整除的点上(即第一个灯笼位于 $$$v$$$ 点,第二个灯笼位于 $$$2v$$$ 点,依此类推)。

也只有一列静止的火车占据了从$$$l$$$到$$$r$$$(含)的所有点。

如果 $$$p$$$ 能被 $$$v$$$整除,并且该位置没有静止的火车,Vova 就可以在 $$$p$$$ 处看到灯笼($$$p \not\in [l; r]$$$)。因此,如果有灯笼的点是静止火车覆盖的点之一,Vova 就看不到这个灯笼。

你的问题是说 Vova 在路径中会看到的灯笼数量。 Vova 计划参加 $$$t$$$ 不同的会议,因此您应该回答 $$$t$$$ 独立的询问。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 查询数。

然后是 $$$t$$$ 行。第 $$$i$$$ 行包含四个整数 $$$L_i, v_i, l_i, r_i$$$ ($$$1 \le L, v \le 10^9$$$, $$$1 \le l \le r \le L$$$) — 第 $$$i$$$ 路径的目的地点、灯笼出现的周期以及静止列车所占用的路段。

输出

打印 $$$t$$$ 行。第 $$$i$$$ 行应包含一个整数 — 第 $$$i$$$ 查询的答案。

示例

输入 #1

4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000

输出 #1

3
0
1134
0

注意

对于第一个示例查询,答案是 $$$3$$$。 $$$2$$$、$$$4$$$、$$$6$$$、$$$8$$$ 和 $$$10$$$ 位置有灯笼,但由于火车静止,Vova 没有看到 $$$4$$$ 和 $$$6$$$ 位置的灯笼。

对于第二个示例查询,答案是 $$$0$$$,因为唯一的灯笼位于 $$$51$$$ 点,并且该点还有一列静止的火车。

对于第三个示例查询,答案是 $$$1134$$$,因为有 $$$1234$$$ 灯笼,但 Vova 没有看到从位置 $$$100$$$ 到位置 $$$199$$$ 之间的灯笼。

对于第四个示例查询,答案是 $$$0$$$,因为静止的火车覆盖了整个路径。