AT_agc044_a.[AGC044A] Pay to Win

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

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

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

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

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

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

第一行包含一个整数。

$ T $

随后的 $T$ 行代表 $T$ 个测试用例，每行包含五个整数。

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

对于每个测试用例，输出一行表示答案。

约束

• $ 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)$。