U541181 数字变换

晓莱现在手上有一个数字$0$ ，他希望你能通过一定的数字进行兑换得到数字$N$。 其中你可以通过以下操作更改数字，但是需要支付一定数量的硬币： - 将当前数乘$2$，需要$A$个硬币。 - 将当前数乘$3$，需要$B$个硬币。 - 将当前数乘$5$，需要$C$个硬币。 - 将当前数加$1$或减$1$，需要$D$个硬币。 你可以按任意顺序和任意次数执行这些操作。 最少需要多少硬币才能得到$N$？ 为了增大题目的难度，设置了$T$组测试用例。

第一行包含一个整数$ T $， 表示测试的组数。 随后的$T$行代表$T$个测试用例。每行包含五个整数。 分别是$ N $， $ A $， $ B $， $ C $， $ D $。

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

对于$50\%$的数据满足，$ 1\ \le\ T\ \le\ 10 $， $ 1\ \le\ N\ \le\ 10^{2} $， $ 1\ \le\ A,\ B,\ C,\ D\ \le\ 10^2 $， $ N,\ A,\ B,\ C,\ D $ 都是整数。 对于$100\%$的数据满足，$ 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 $ 都是整数。 保证 $N \times D < 2^{64}$ 。 ## 样例解释 对于第一个测试用例，达到最低成本$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)$