徒步的其中一天恰逢假期,所以晚上在营地,决定安排一场喜庆的烟花表演。为此,徒步旅行的组织者购买了两个烟花发射装置和大量的发射弹。
两个安装同时打开。第一个安装每 $$$a$$$ 分钟发射烟花(即发射后 $$$a、2 \cdot a、3 \cdot a、\dots$$$ 分钟后)。第二个装置每 $$$b$$$ 分钟发射一次烟花(即发射后 $$$b, 2 \cdot b, 3 \cdot b, \dots$$$ 分钟后)。
每个烟花在发射后 $$$m + 1$$$ 分钟内在天空中可见,即,如果烟花在安装开启后 $$$x$$$ 分钟后发射,则从 $$$x$$$ 到 $$$x + m$$$(含)期间每分钟都可见。如果一枚烟花在 $$$m$$$ 分钟后发射,则两枚烟花都会持续一分钟可见。
天空中同时最多可以看到多少烟花?
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。
每个测试用例的第一行也是唯一一行包含整数 $$$a$$$、$$$b$$$、$$$m$$$ ($$$1 \le a, b, m \le 10^{18}$$$) - 第一次安装、第二次安装的发射频率以及烟花在天空中可见的时间。
输出
对于每组输入数据,输出一个数字——可以同时看到的烟花的最大数量。
示例
输入 #1
6 6 7 4 3 4 10 7 8 56 5 6 78123459896 1 1 1 1 1 1000000000000000000
输出 #1
2 7 17 28645268630 4 2000000000000000002
注意
在第一组输入数据中,烟花在天空中可见的时间为 $$$5$$$ 分钟。由于第一个装置每 $$$6$$$ 分钟发射一次烟花,第二个装置每 $$$7$$$ 分钟发射一次烟花,因此从同一装置发射的两枚烟花将不会同时在天空中可见。同时,在假期开始 $$$7$$$ 分钟后,将看到来自第一个营地的烟花和来自第二个营地的烟花。因此,同时观看的烟花数量不会超过 $$$2$$$。
在第三组输入数据中,$$$17$$$ 烟花将在 $$$112$$$ 分钟后可见:
- 首次安装时有时会发射 $$$9$$$ 烟花 [$$$56, 63, 70, 77, 84, 91, 98, 105, 112$$$];
- 第二个装置有时会发射 $$$8$$$ 烟花 [$$$56, 64, 72, 80, 88, 96, 104, 112$$$]。