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$$$,因为静止的火车覆盖了整个路径。