Little G 准备玩 $n$ 局游戏。

Little G 是游戏之王。如果他想赢，他一定能赢下一局。但如果他不在乎输赢，由于运气不好，他会输掉一局。Little G 的期望胜率为 $x = \frac{a}{b}$。在进行第 $i$ 局游戏时，如果他当前的胜率小于或等于 $x$，他就会渴望胜利并轻松赢得比赛。否则，他会享受比赛并输掉比赛。

给定 $n, a, b$，Little G 想知道他总共会赢多少局游戏。

注意，在进行第一局游戏时，胜率被视为 $0$。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 100000$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含三个整数 $n, a, b$ ($1 \le n \le 10^9, 0 \le a \le b \le 10^9, b \neq 0$)，表示一个测试用例。

输出格式

输出 $T$ 行。每行输出一个整数，表示对应测试用例的答案。

样例

样例输入 1

3
4 3 5
8 7 10
1 1 3

样例输出 1

2
5
1

说明

在第一个测试用例中，$x = \frac{3}{5} = 0.6$：

• 进行第一局游戏时，胜率 $= 0 \le x$，所以 Little G 会赢下比赛；
• 进行第二局游戏时，胜率 $= \frac{1}{1} > x$，所以 Little G 会输掉比赛；
• 进行第三局游戏时，胜率 $= \frac{1}{2} \le x$，所以 Little G 会赢下比赛；
• 进行第四局游戏时，胜率 $= \frac{2}{3} > x$，所以 Little G 会输掉比赛。

总共，Little G 会赢 2 局游戏，这就是第一个测试用例的答案。