Problem Statement

We have an integer $P=0$. Find the minimum total cost to make $P=N$ by doing the following three kinds of operations any number of times in any order.

• Increase $P$ by $1$, at a cost of $X$.
• Increase $P$ by $A$, at a cost of $Y$.
• Increase $P$ by $B$, at a cost of $Z$.

Solve each of the $T$ test cases given to you.

Constraints

• $1 \le T \le 100$
• $1 \le N,A,B,X,Y,Z \le 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is in the following format:

N\ A\ B\ X\ Y\ Z

Output

Print $T$ lines, the $i$-th of which should contain the answer to $\mathrm{case}_i$.