题目描述

你有一个数字 $0$ ，你希望得到数字 $N$。

你可以通过以下操作更改数字，每次操作都需要支付一定数量的硬币：

• 将当前数乘 $2$，需要 $A$ 个硬币。
• 将当前数乘 $3$，需要 $B$ 个硬币。
• 将当前数乘 $5$，需要 $C$ 个硬币。
• 将当前数加 $1$ 或减 $1$，需要 $D$ 个硬币。

你可以按任意顺序和任意次数执行这些操作。

最少需要多少硬币才能得到 $N$？

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

输入格式

第一行包含一个整数。

$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

输出

20
19
26
3821859835
23441258666

说明/提示

约束

• $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$ 都是整数。

样例解释

对于第一个测试用例，达到最低成本 $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)$。