Chocolate

• BUET CSE FEST’23 has come to an end!!!! Chimatu Can’t stop crying as he already started to miss the festive vibe so much. To make him happy again you need to buy some chocolates for him. But yeah you are a well known miserable person, and so that you want to spend as less money as you can.

Now comes the real problem. You need to buy $n$ chocolates.

You can buy $2$ types of chocolates. Each type has a infinite amount of chocolates.

The first type chocolate has an initial price $p$, where the second type chocolate has an initial price $q$.

Each time one buys a chocolate of the first type, the price of this type gets decreased by $x$. Similarly, each time a second type chocolate is bought, the price of this type gets decreased by $y$.

Say $p = 9$ and $x = 3$ for the first type of chocolate. Currently the price is $9$. After buying one chocolate the price decreases by $3$ and now the new price is $6$. After buying another chocolate the price will again decrease by $3$ and the new price will be $3$.

You have to find the minimum cost to buy $n$ chocolates and make Chimatu happy!!!

[Note: It is guaranteed that the price of any chocolate will never be negative]

Input

The first line of the input contains an integer $t$ denoting the number of test cases.

The next line of each test case contains 5 space separated integers.

• $n$- The amount of chocolates to be bought.

• $p$- The initial price of first type chocolate

• $q$- The initial price of second type chocolate

• $x$- The amount of price reduces after buying each chocolate of first type

• $y$- The amount of price reduces after buying each chocolate of second type

Constraints

$1 \le t \le 10^5$

$1 \le n \le 10^6$

$1 \le x\le p \le 10 ^ 7$

$1\le y\le q\le 10 ^ 7$

Output

The output should contain $t$ lines. $i$th line of output should contain the minimum cost for $i$th test case.

Sample

Input	Output
1 5 100 50 5 3	220