Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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$$$ минут после другого, то в течение одной минуты будут видны оба салюта.

Какое максимальное количество салютов одновременно можно увидеть в небе?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой и единственной строке каждого набора входных данных содержатся натуральные числа $$$a$$$, $$$b$$$, $$$m$$$ ($$$1 \le a, b, m \le 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$$$ фейерверков:

  • $$$9$$$ фейерверков, запущенных из первой установки в моменты [$$$56, 63, 70, 77, 84, 91, 98, 105, 112$$$];
  • $$$8$$$ фейерверков, запущенных из второй установки в моменты [$$$56, 64, 72, 80, 88, 96, 104, 112$$$].