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