题目描述

你正在玩一个非常流行的游戏，名为 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$ 个火把所需的最少交易次数。保证在给定的约束条件下答案总是存在。

说明/提示

由 ChatGPT 4.1 翻译

样例

5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000

14
33
25
2000000003
1000000001999999999