题目描述

你从数字 $0$ 开始，想要达到数字 $N$。

你可以通过以下操作改变数字，并支付一定数量的硬币：

• 将数字乘以 $2$，支付 $A$ 个硬币。
• 将数字乘以 $3$，支付 $B$ 个硬币。
• 将数字乘以 $5$，支付 $C$ 个硬币。
• 将数字加 $1$ 或减 $1$，支付 $D$ 个硬币。

你可以以任意顺序执行这些操作，并且可以执行任意次数。

你需要花费多少个硬币才能达到数字 $N$？

你需要解决 $T$ 个测试用例。

约束条件

• $1 \le T \le 10$
• $1 \le N \le 10^{18}$
• $1 \le A, B, C, D \le 10^9$
• 所有数字 $N, A, B, C, D$ 都是整数。

输入

输入以以下格式从标准输入中给出：

$T$

接下来，$T$ 行描述 $T$ 个测试用例。每行的格式如下所示：

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

输出

对于每个测试用例，在标准输出中打印答案，然后换行。

示例输入 1

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

示例输出 1

20
19
26
3821859835
23441258666

对于第一个测试用例，以下移动序列可以达到最小花费 $20$：

• 初始时 $x = 0$。
• 支付 $8$ 个硬币将数字增加 $1$（$x = 1$）。
• 支付 $1$ 个硬币将数字乘以 $2$（$x = 2$）。
• 支付 $1$ 个硬币将数字乘以 $2$（$x = 4$）。
• 支付 $2$ 个硬币将数字乘以 $3$（$x = 12$）。
• 支付 $8$ 个硬币将数字减少 $1$（$x = 11$）。

对于第二个测试用例，以下移动序列可以达到最小花费 $19$：

• 初始时 $x = 0$。
• 支付 $8$ 个硬币将数字增加 $1$（$x = 1$）。
• 支付 $1$ 个硬币将数字乘以 $2$（$x = 2$）。
• 支付 $2$ 个硬币将数字乘以 $5$（$x = 10$）。
• 支付 $8$ 个硬币将数字增加 $1$（$x = 11$）。