Problem Description

You are given three non-negative integers $x, a, b$. As long as $x \ge 0$, you may perform the following operation on $x$ any number of times (including $0$ times):

• Change $x$ to $ax - b$.

You need to find the minimum value of $x$ that you can obtain through these operations.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, one line contains three integers $x, a, b$.

Output Format

For each test case, output one integer per line, the answer.

2
6 2 4
5 3 16

6
-1

Hint

Sample explanation: For the first test case, $x = 6 \rightarrow 8 \rightarrow 12 \rightarrow \cdots$. Obviously, $x = 6$ is the minimum value.

For the second test case, $x = 5 \rightarrow -1$, and $x = -1$ is the minimum value.

Constraints:

For $30\%$ of the testdata, $T \le 5$, and $x, a, b \le 100$.

For another $20\%$ of the testdata, $a > b$.

For another $20\%$ of the testdata, $b = 0$.

For $100\%$ of the testdata, $1 \le T \le 1000$, and $0 \le x, a, b \le 10^{9}$.

Translated by ChatGPT 5