Limits 1s, 512 MB
  • 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 nn chocolates.

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

The first type chocolate has an initial price pp, where the second type chocolate has an initial price qq.

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

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

You have to find the minimum cost to buy nn 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 tt denoting the number of test cases.

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

  • nn- The amount of chocolates to be bought.

  • pp- The initial price of first type chocolate

  • qq- The initial price of second type chocolate

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

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

Constraints

1t1051 \le t \le 10^5

1n1061 \le n \le 10^6

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

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

Output

The output should contain tt lines. iith line of output should contain the minimum cost for iith test case.

Sample

InputOutput
1
5 100 50 5 3
220

Submit

Login to submit.

Statistics

75% Solution Ratio
AbdurRahman_40Earliest, 8M ago
The_crawlerFastest, 0.0s
Mr.WHiTELightest, 5.1 MB
user.7760Shortest, 236B
Toph uses cookies. By continuing you agree to our Cookie Policy.