测试数据来自 system/2953

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　两个烟花发射装置同时开启。第一个装置每隔 \(a\) 分钟发射一次烟花。第二个装置每 \(b\) 分钟发射一次烟花。

　　每个烟花在发射后的 \(m+1\) 分钟内都可以在天空中看到，也就是说，如果一个烟花是在装置开启后的 \(x\) 分钟后发射的，那么从 \(x\) 到 \(x+m\) (包括首尾两分钟)的每一分钟都可以看到该烟花。如果一个烟花在另一个烟花 \(m\) 分钟后发射，则两个烟花都将在一分钟内可见。

　　求天空中最多可以同时看到多少枚烟花？

【输入格式】

　　每个测试由多个测试用例组成。第一行包含一个整数 \(t (1≤t≤10^4)\) - 测试用例的数量。
　　每个测试用例包含三个数 \(a 、b 、m （1≤a,b,m≤10^18）\)--第一个烟花发射装置、第二个烟花发射装置的发射频率，以及烟花在天空中可见的时间。

【输出格式】

　　对于每组数据输出一个整数，表示同时能看到烟花的最大数量。

【输入输出样例】

　Input

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

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤t≤10^4\)，\(1≤a,b,m≤10^{18}\)。

【来源】

　　Mr.he