小婷老师给出四个整数 $n$、$B$、$x$、$y$，并从 $a_0=0$ 开始构造数列

对于每个 $i\ge1$，新的一项只能从两种结果中选择：

• $a_i=a_{i-1}+x$；
• $a_i=a_{i-1}-y$。

整列数必须始终满足 $a_i\le B$。在这个条件下，成绩按 $\sum_{i=0}^{n}a_i$ 计算，系统会采用能够让总和达到最大的构造，并记录这个最大总和。每组输入相互独立。

输入格式

第一行一个整数 $t$，表示测试用例数量。随后 $t$ 行，每行包含四个整数 $n$、$B$、$x$、$y$。

输出格式

对每个测试用例输出一行，给出满足条件时可能取得的最大数列总和。

3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3

15
4000000000
-10

1
5 10 3 2

35

2
1 1 1 1
3 5 2 4

1
6

样例解释

第一组可以得到 $[0,1,2,3,4,5]$，总和为 $15$；第二组的最优数列在 $0$ 与 $10^9$ 之间交替；第三组可得到 $[0,-3,-6,1,-2]$。

数据范围与约定

• $1\le t\le10^4$
• $1\le n\le2\times10^5$
• $1\le B,x,y\le10^9$
• 所有测试用例的 $n$ 之和不超过 $2\times10^5$