您正在玩一款非常流行的游戏,名为 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$$$ 火把所需的最少交易次数。在给定的约束条件下,答案总是存在的。
示例
输入 #1
5 2 1 5 42 13 24 12 11 12 1000000000 1000000000 1000000000 2 1000000000 1000000000
输出 #1
14 33 25 2000000003 1000000001999999999