题目描述

有一天徒步旅行正好遇上了节日，所以傍晚在营地决定举办一场盛大的烟花表演。为此，徒步组织者购买了两台烟花发射装置和大量烟花弹。

两台装置会同时启动。第一台装置每隔 $a$ 分钟发射一次烟花（即在启动后 $a, 2a, 3a, \dots$ 分钟时发射）。第二台装置每隔 $b$ 分钟发射一次烟花（即在启动后 $b, 2b, 3b, \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}$），分别表示第一台装置的发射间隔、第二台装置的发射间隔，以及每个烟花在天空中可见的时间。

输出格式

对于每组输入数据，输出一个整数，表示同一时刻天空中最多能同时看到的烟花数量。

说明/提示

在第一组输入数据中，烟花在天空中可见 $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$ 个烟花。

由 ChatGPT 4.1 翻译

样例

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