Limits 1s, 512 MB

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]


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.


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


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


5 100 50 5 3