Вы играете в очень популярную игру, которая называется Cubecraft. Изначально у вас в инвентаре находится одна палка и вы хотите скрафтить \(k\) факелов. Один факел можно скрафтить при помощи одной палки и одного угля.
К счастью, вы встретили очень щедрого странствующего торговца, у которого есть два предложения для обмена:
- обменять \(1\) палку на \(x\) палок (вы теряете \(1\) палку и получаете \(x\) палок).
- обменять \(y\) палок на \(1\) уголь (вы теряете \(y\) палок и получаете \(1\) уголь).
В течение одного обмена вы можете использовать только одно из этих двух предложений. Вы можете использовать любые предложения для обмена сколько угодно раз, в любом порядке.
Ваша задача — найти минимальное количество обменов, которое вам необходимо совершить, чтобы вы смогли скрафтить хотя бы \(k\) факелов. Ответ всегда существует при заданных ограничениях.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Выведите ответ на каждый набор тестовых данных: минимальное количество обменов, которое вам необходимо совершить, чтобы вы смогли скрафтить хотя бы \(k\) факелов. Ответ всегда существует при заданных ограничениях.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000
|
14
33
25
2000000003
1000000001999999999
|