{"raw_statement":[{"iden":"problem statement","content":"You start with the number $0$ and you want to reach the number $N$.\nYou can change the number, paying a certain amount of coins, with the following operations:\n\n*   Multiply the number by $2$, paying $A$ coins.\n*   Multiply the number by $3$, paying $B$ coins.\n*   Multiply the number by $5$, paying $C$ coins.\n*   Increase or decrease the number by $1$, paying $D$ coins.\n\nYou can perform these operations in arbitrary order and an arbitrary number of times.\nWhat is the minimum number of coins you need to reach $N$?\n**You have to solve $T$ testcases.**"},{"iden":"constraints","content":"*   $1 \\le T \\le 10$\n*   $1 \\le N \\le 10^{18}$\n*   $1 \\le A, B, C, D \\le 10^9$\n*   All numbers $N, A, B, C, D$ are integers."},{"iden":"input","content":"The input is given from Standard Input. The first line of the input is\n\n$T$\n\nThen, $T$ lines follow describing the $T$ testcases. Each of the $T$ lines has the format\n\n$N$ $A$ $B$ $C$ $D$"},{"iden":"sample input 1","content":"5\n11 1 2 4 8\n11 1 2 2 8\n32 10 8 5 4\n29384293847243 454353412 332423423 934923490 1\n900000000000000000 332423423 454353412 934923490 987654321"},{"iden":"sample output 1","content":"20\n19\n26\n3821859835\n23441258666\n\nFor the first testcase, a sequence of moves that achieves the minimum cost of $20$ is:\n\n*   Initially $x = 0$.\n*   Pay $8$ to increase by $1$ ($x = 1$).\n*   Pay $1$ to multiply by $2$ ($x = 2$).\n*   Pay $1$ to multiply by $2$ ($x = 4$).\n*   Pay $2$ to multiply by $3$ ($x = 12$).\n*   Pay $8$ to decrease by $1$ ($x = 11$).\n\nFor the second testcase, a sequence of moves that achieves the minimum cost of $19$ is:\n\n*   Initially $x = 0$.\n*   Pay $8$ to increase by $1$ ($x = 1$).\n*   Pay $1$ to multiply by $2$ ($x = 2$).\n*   Pay $2$ to multiply by $5$ ($x = 10$).\n*   Pay $8$ to increase by $1$ ($x = 11$)."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}