波利卡普花了一整天的时间为您准备问题。现在他必须睡至少 $$$a$$$ 分钟才能感到精神焕发。
波利卡普只能通过听到闹钟的声音醒来。所以他刚刚睡着了,他的第一个闹钟在 $$$b$$$ 分钟后响起。
每次波利卡普醒来时,他都会决定是否要再睡一会儿。如果他总共睡了不到 $$$a$$$ 分钟,那么他会将闹钟设置为在重置后 $$$c$$$ 分钟内响起,并花费 $$$d$$$ 分钟再次入睡。否则,他就会起床继续这一天。
如果波利卡普入睡时闹钟响起,那么他会将闹钟重置为在 $$$c$$$ 分钟后响起,并尝试再次入睡 $$$d$$$ 分钟。
你只是想知道波利卡普什么时候会起床或者报告说这永远不会发生。
请查看注释以获取示例的一些解释。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含四个整数 $$$a, b, c, d$$$ ($$$1 \le a, b, c, d \le 10^9$$$) — Polycarp 必须睡觉才能感到精神焕发的时间、第一个闹钟响起之前的时间、每个后续闹钟响起之前的时间以及 Polycarp 入睡所花费的时间。
输出
对于每个测试用例打印一个整数。如果波利卡普从不下床,则打印 -1。否则,打印波利卡普起床所需的时间。
示例
输入 #1
7 10 3 6 4 11 3 6 4 5 9 4 10 6 5 2 3 1 1 1 1 3947465 47342 338129 123123 234123843 13 361451236 361451000
输出 #1
27 27 9 -1 1 6471793 358578060125049
注意
在第一个测试用例中,Polycarp 在 $$$3$$$ 分钟后醒来。在他需要的 $$$10$$$ 分钟中,他只休息了 $$$3$$$ 分钟。因此,在那之后,他将闹钟设置为在 $$$6$$$ 分钟内响起,并花了 $$$4$$$ 分钟入睡。因此,他多休息了 $$$2$$$ 分钟,总共睡眠 $$$3+2=5$$$ 分钟。然后他又重复该过程 3 次,最终获得 $$$11$$$ 分钟的睡眠。最后,他从床上起来。他在第一个闹钟响之前花了 $$$3$$$ 分钟,然后四次重置了闹钟。答案是$$$3+4 \cdot 6 = 27$$$。
第二个例子几乎与第一个例子相似,但 Polycarp 需要 $$$11$$$ 分钟的睡眠,而不是 $$$10$$$。然而,这并没有改变什么,因为无论如何,他在使用这些警报参数时都会获得 $$$11$$$ 分钟的时间。
在第三个测试用例中,Polycarp 在第一个警报后醒来,休息得很好。因此,答案是$$$b=9$$$。
在第四个测试用例中,Polycarp 在 $$$5$$$ 分钟后醒来。不幸的是,他不断地重置闹钟,甚至一分钟都无法休息:(