A. 除法与取模

x%0=x/0=o.O

给定 $x,a,b$ ，求出对于所有的 $y$ 为整数且 $y\in[1,10^9]$ 的 $a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloor$ 的最大值。

其中 $\lfloor b\rfloor$ 的意思是对于 $b$ 向下取整，例如 $\lfloor \frac{7}{3}\rfloor=2$。

其中 $a\%b$ 的意思是 $a$ 对 $b$ 取余数，例如 $7\%3=1$。

第一行，一个整数 $t(1\le t \le 10^5)$ 代表数据组数。

对于每组数据，仅有一行 $3$ 个整数 $x,a,b(0\le x,a,b \le 10^6)$，含义如题目所示。

保证同一测试点内的 $x$、$a$、$b$ 的和均不会超过 $10^6$。

对于每组数据，输出一行整数代表对于所有的 $y$ 为整数且 $y\in[1,10^9]$ 的 $a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloor$ 的最大值。

输入样例

5
0 0 0
1 0 0
1 0 1
2 3 0
3 1 2 

输出样例

0
0
1
6
6