B. 烟花

每个测试用例时间限制：1秒 每个测试用例内存限制：256兆字节

徒步旅行的一天恰逢节日，因此晚上在营地，大家决定举办一场盛大的烟花表演。为此，徒步活动的组织者购买了两台烟花发射装置和数量庞大的发射弹丸。

两台装置同时启动。

• 第一台装置每隔 $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$ 分钟，那么两发烟花会有1分钟同时可见。

请问：同一时间在空中最多能看到多少发烟花？

输入格式

输入包含多组测试数据。 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 表示测试用例的数量。 接下来每行描述一个测试用例： 每行包含三个整数 $a, b, m$ ($1 \le a,b,m \le 10^{18}$)。

• $a$：第一台装置的发射间隔
• $b$：第二台装置的发射间隔
• $m$：烟花发射后，除发射时刻外的持续可见时长

输出格式

对于每个测试用例，输出一个整数 —— 同一时间能看到的最大烟花数量。

样例输入

6
6 7 4
3 4 10
7 8 56
5 6 78123459896
1 1 1
1 1 1000000000000000000

样例输出

2
7
17
28645268630
4
2000000000000000002

样例说明

1. 第一个测试用例：烟花在空中可见时长为 $5$ 分钟。第一台装置每 $6$ 分钟发射一发，第二台每 $7$ 分钟发射一发，同一台装置发射的烟花不会同时出现。在启动后第 $7$ 分钟，能同时看到来自两台装置各一发烟花，因此最多看到 $2$ 发。

2. 第三个测试用例：在第 $112$ 分钟时能看到 $17$ 发烟花：

   • 第一台装置发射的 $9$ 发：发射时间 $[56,63,70,77,84,91,98,105,112]$
   • 第二台装置发射的 $8$ 发：发射时间 $[56,64,72,80,88,96,104,112]$