← 返回题目列表

Codeforces · 1418/A

A. 购买火把

中文机器翻译题面 查看原题

您正在玩一款非常流行的游戏,名为 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