A. Покупка факелов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в очень популярную игру, которая называется Cubecraft. Изначально у вас в инвентаре находится одна палка и вы хотите скрафтить $$$k$$$ факелов. Один факел можно скрафтить при помощи одной палки и одного угля.

К счастью, вы встретили очень щедрого странствующего торговца, у которого есть два предложения для обмена:

  • обменять $$$1$$$ палку на $$$x$$$ палок (вы теряете $$$1$$$ палку и получаете $$$x$$$ палок).
  • обменять $$$y$$$ палок на $$$1$$$ уголь (вы теряете $$$y$$$ палок и получаете $$$1$$$ уголь).

В течение одного обмена вы можете использовать только одно из этих двух предложений. Вы можете использовать любые предложения для обмена сколько угодно раз, в любом порядке.

Ваша задача — найти минимальное количество обменов, которое вам необходимо совершить, чтобы вы смогли скрафтить хотя бы $$$k$$$ факелов. Ответ всегда существует при заданных ограничениях.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Единственная строка набора тестовых данных содержит три целых числа $$$x$$$, $$$y$$$ и $$$k$$$ ($$$2 \le x \le 10^9$$$; $$$1 \le y, k \le 10^9$$$) — количество палок, которые вы можете купить за одну палку, количество палок, необходимое для покупки одного угля, и количество факелов, которые вам нужно скрафтить, соответственно.

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

Выведите ответ на каждый набор тестовых данных: минимальное количество обменов, которое вам необходимо совершить, чтобы вы смогли скрафтить хотя бы $$$k$$$ факелов. Ответ всегда существует при заданных ограничениях.

Пример
Входные данные
5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000
Выходные данные
14
33
25
2000000003
1000000001999999999