311177: CF1945B. Fireworks

B. Fireworkstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

One of the days of the hike coincided with a holiday, so in the evening at the camp, it was decided to arrange a festive fireworks display. For this purpose, the organizers of the hike bought two installations for launching fireworks and a huge number of shells for launching.

Both installations are turned on simultaneously. The first installation launches fireworks every $a$ minutes (i.e., after $a, 2 \cdot a, 3 \cdot a, \dots$ minutes after launch). The second installation launches fireworks every $b$ minutes (i.e., after $b, 2 \cdot b, 3 \cdot b, \dots$ minutes after launch).

Each firework is visible in the sky for $m + 1$ minutes after launch, i.e., if a firework was launched after $x$ minutes after the installations were turned on, it will be visible every minute from $x$ to $x + m$, inclusive. If one firework was launched $m$ minutes after another, both fireworks will be visible for one minute.

What is the maximum number of fireworks that could be seen in the sky at the same time?

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.

The first and only line of each test case contains integers $a$, $b$, $m$ ($1 \le a, b, m \le 10^{18}$) — the frequency of launching for the first installation, the second installation, and the time the firework is visible in the sky.

Output

For each set of input data, output a single number — the maximum number of fireworks that can be seen simultaneously.

ExampleInput

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

Output

2
7
17
28645268630
4
2000000000000000002

Note

In the first set of input data, the fireworks are visible in the sky for $5$ minutes. Since the first installation launches fireworks every $6$ minutes, and the second one every $7$ minutes, two fireworks launched from the same installation will not be visible in the sky at the same time. At the same time, after $7$ minutes from the start of the holiday, one firework from the first and one from the second camp will be visible. Thus, it is possible to see no more than $2$ fireworks simultaneously.

In the third set of input data, $17$ fireworks will be visible after $112$ minutes:

• $9$ fireworks launched from the first installation at times [$56, 63, 70, 77, 84, 91, 98, 105, 112$];
• $8$ fireworks launched from the second installation at times [$56, 64, 72, 80, 88, 96, 104, 112$].

题目大意：
在徒步旅行中的一天与节日重合，因此决定在营地的晚上安排一场节日烟花表演。为此，徒步旅行组织者购买了两套烟花发射装置和大量的烟花弹。

两套发射装置同时启动。第一套装置每隔a分钟发射一次烟花（即启动后a、2*a、3*a...分钟发射）。第二套装置每隔b分钟发射一次烟花（即启动后b、2*b、3*b...分钟发射）。

每个烟花在发射后m+1分钟内可见，即如果某个烟花在启动x分钟后发射，它将在x到x+m分钟内每分钟可见。如果一个烟花在另一个烟花发射m分钟后发射，两个烟花将同时可见一分钟。

问：在天空中可以同时看到的最多的烟花数量是多少？

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行（也是唯一一行）包含三个整数a、b、m（1≤a，b，m≤10^18）——第一套装置的发射频率、第二套装置的发射频率和烟花在天空中可见的时间。

输出数据格式：
对于每组输入数据，输出一个数字——可以同时看到的最多的烟花数量。

示例：
输入：
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

注意：
在第一组输入数据中，烟花在天空中可见5分钟。由于第一套装置每6分钟发射一次烟花，第二套装置每7分钟发射一次烟花，同一装置发射的两个烟花不会同时在天空中可见。同时，在节日开始后7分钟，将可以看到来自第一套和第二套装置的一个烟花。因此，可以同时看到不超过2个烟花。

在第三组输入数据中，112分钟后可以看到17个烟花：
- 第一套装置在时刻[56, 63, 70, 77, 84, 91, 98, 105, 112]发射了9个烟花；
- 第二套装置在时刻[56, 64, 72, 80, 88, 96, 104, 112]发射了8个烟花。题目大意： 在徒步旅行中的一天与节日重合，因此决定在营地的晚上安排一场节日烟花表演。为此，徒步旅行组织者购买了两套烟花发射装置和大量的烟花弹。 两套发射装置同时启动。第一套装置每隔a分钟发射一次烟花（即启动后a、2*a、3*a...分钟发射）。第二套装置每隔b分钟发射一次烟花（即启动后b、2*b、3*b...分钟发射）。 每个烟花在发射后m+1分钟内可见，即如果某个烟花在启动x分钟后发射，它将在x到x+m分钟内每分钟可见。如果一个烟花在另一个烟花发射m分钟后发射，两个烟花将同时可见一分钟。 问：在天空中可以同时看到的最多的烟花数量是多少？ 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行（也是唯一一行）包含三个整数a、b、m（1≤a，b，m≤10^18）——第一套装置的发射频率、第二套装置的发射频率和烟花在天空中可见的时间。 输出数据格式： 对于每组输入数据，输出一个数字——可以同时看到的最多的烟花数量。 示例： 输入： 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 注意： 在第一组输入数据中，烟花在天空中可见5分钟。由于第一套装置每6分钟发射一次烟花，第二套装置每7分钟发射一次烟花，同一装置发射的两个烟花不会同时在天空中可见。同时，在节日开始后7分钟，将可以看到来自第一套和第二套装置的一个烟花。因此，可以同时看到不超过2个烟花。 在第三组输入数据中，112分钟后可以看到17个烟花： - 第一套装置在时刻[56, 63, 70, 77, 84, 91, 98, 105, 112]发射了9个烟花； - 第二套装置在时刻[56, 64, 72, 80, 88, 96, 104, 112]发射了8个烟花。