题目描述

你有三个非负整数 $x,a,b$。在 $x \ge 0$ 的前提下，你可以对 $x$ 进行任意次（包括 $0$ 次）如下操作：

• 将 $x$ 变为 $ax - b$。

你需要求出你通过操作能得到的 $x$ 的最小值。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据，输入一行三个整数 $x,a,b$。

输出格式

对于每组数据，输出一行一个整数表示答案。

2
6 2 4
5 3 16

6
-1

提示

样例解释：对于第一组数据，有 $x=6 \rightarrow 8 \rightarrow 12 \rightarrow \cdots$，很明显 $x=6$ 就是最小值。

对于第二组数据，有 $x=5\rightarrow -1$，$x=-1$ 为最小值。

对于 $30\%$ 的数据，$T \le 5$，$x,a,b \le 100$。

对于另 $20\%$ 的数据，$a \gt b$。

对于另 $20\%$ 的数据，$b=0$。

对于 $100\%$ 的数据，$1 \le T \le 1000$，$0 \le x,a,b \le 10^{9}$。