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

Description

徒步旅行的其中一天碰巧是假期，所以在营地的晚上，决定举办一个节日烟火表演。为此，徒步旅行的组织者购买了两个发射烟火的装置和大量的烟火弹。

两个装置同时启动。第一个装置每隔aa分钟发射一次烟火（即在启动后a,2⋅a,3⋅a,…a,2⋅a,3⋅a,…分钟后）。第二个装置每隔b分钟发射一次烟火（即在启动后b,b⋅2,b⋅3,b⋅4...分钟后）。

每个烟火发射后在天空中可见m+1分钟，即如果一个烟火是在装置启动后x分钟后发射的，它将在x到x+m分钟内每分钟可见一次。如果一个烟火是在另一个烟火发射m分钟后发射的，那么两个烟火将同时可见一分钟。

在同一时间天空中最多可以看到多少个烟火？

输入

每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤1e4）— 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含整数a、b、m（1≤a,b,m≤1e18）— 第一个装置发射的频率、第二个装置发射的频率和烟火在天空中可见的时间。

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

Note

在第一组输入数据中，烟火在天空中可见5分钟。由于第一个装置每隔6分钟发射一次烟火，第二个装置每隔7分钟发射一次，从同一个装置发射的两个烟火不会同时出现在天空中。同时，在假期开始后7分钟，第一个装置和第二个装置各发射一个烟火将同时可见。因此，同时最多可以看到2个烟火。

在第三组输入数据中，112分钟时将可见17个烟火：

• 9个烟火是从第一个装置在时刻[56,63,70,77,84,91,98,105,112]发射的；
• 8个烟火是从第二个装置在时刻[56,64,72,80,88,96,104,112]发射的。