x%0=x/0=o.O
给定 x,a,bx,a,bx,a,b ，求出对于所有的 yyy 为整数且 y∈[1,109]y\in[1,10^9]y∈[1,109] 的 a×(x%y)+b×⌊xy⌋a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloora×(x%y)+b×⌊yx⌋ 的最大值。
其中 ⌊b⌋\lfloor b\rfloor⌊b⌋ 的意思是对于 bbb 向下取整，例如 ⌊73⌋=2\lfloor \frac{7}{3}\rfloor=2⌊37⌋=2。
其中 a%ba\%ba%b 的意思是 aaa 对 bbb 取余数，例如 7%3=17\%3=17%3=1。
第一行，一个整数 t(1≤t≤105)t(1\le t \le 10^5)t(1≤t≤105) 代表数据组数。
对于每组数据，仅有一行 333 个整数 x,a,b(0≤x,a,b≤106)x,a,b(0\le x,a,b \le 10^6)x,a,b(0≤x,a,b≤106)，含义如题目所示。
保证同一测试点内的 xxx、aaa、bbb 的和均不会超过 10610^6106。
对于每组数据，输出一行整数代表对于所有的 yyy 为整数且 y∈[1,109]y\in[1,10^9]y∈[1,109] 的 a×(x%y)+b×⌊xy⌋a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloora×(x%y)+b×⌊yx⌋ 的最大值。
输入样例
5 0 0 0 1 0 0 1 0 1 2 3 0 3 1 2
输出样例
0 0 1 6 6
