Score : $400$ points

Problem Statement

You start with the number $0$ and you want to reach the number $N$.

You can change the number, paying a certain amount of coins, with the following operations:

• Multiply the number by $2$, paying $A$ coins.
• Multiply the number by $3$, paying $B$ coins.
• Multiply the number by $5$, paying $C$ coins.
• Increase or decrease the number by $1$, paying $D$ coins.

You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach $N$?

You have to solve T testcases.

Constraints

• $1 \le T \le 10$
• $1 \le N \le 10^{18}$
• $1 \le A, B, C, D \le 10^9$
• All numbers $N, A, B, C, D$ are integers.

Input

The input is given from Standard Input. The first line of the input is

$T$

Then, $T$ lines follow describing the $T$ testcases. Each of the $T$ lines has the format

$N$ $A$ $B$ $C$ $D$

Output

For each testcase, print the answer on Standard Output followed by a newline.

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of $20$ is:

• Initially $x = 0$.
• Pay $8$ to increase by $1$ ($x = 1$).
• Pay $1$ to multiply by $2$ ($x = 2$).
• Pay $1$ to multiply by $2$ ($x = 4$).
• Pay $2$ to multiply by $3$ ($x = 12$).
• Pay $8$ to decrease by $1$ ($x = 11$).

For the second testcase, a sequence of moves that achieves the minimum cost of $19$ is:

• Initially $x = 0$.
• Pay $8$ to increase by $1$ ($x = 1$).
• Pay $1$ to multiply by $2$ ($x = 2$).
• Pay $2$ to multiply by $5$ ($x = 10$).
• Pay $8$ to increase by $1$ ($x = 11$).