题目描述

あなたは $0$ という数を持っており、これを $N$ に変えようとしています。

あなたが持っている数は、以下の操作により、定まった枚数のコインを支払うことで変化させることができます。

• $A$ 枚のコインを支払い、持っている数を $2$ 倍する。
• $B$ 枚のコインを支払い、持っている数を $3$ 倍する。
• $C$ 枚のコインを支払い、持っている数を $5$ 倍する。
• $D$ 枚のコインを支払い、持っている数を $1$ 増やす、または $1$ 減らす。

これらの操作は、任意の順に何度でも行うことができます。

持っている数を $N$ とするには、最小で何枚のコインが必要でしょうか。

$T$ 個のテストケースについて答えてください。

输入格式

入力は標準入力から与えられる。入力の $1$ 行目は以下の通りである。

$T$

そして、続く $T$ 行が $T$ 個のテストケースを表す。 これらはそれぞれ以下の形式の行である。

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

输出格式

各テストケースに対し、答えを標準出力に出力せよ。テストケースごとに改行すること。

题目大意

[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

样例输入 #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

提示

约束

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

Sample Explanation 1

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

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$ はすべて整数である。

Sample Explanation 1

$1$ 個目のテストケースで、必要な最小枚数である $20$ 枚のコインで目標を達成する方法は以下の通りです。 - はじめ、持っている数 (以下、これを $x$ とする) は $0$ である。 - $8$ 枚のコインを支払い、$x$ を $1$ 増やす ($x\ =\ 1$)。 - $1$ 枚のコインを支払い、$x$ を $2$ 倍する ($x\ =\ 2$)。 - $1$ 枚のコインを支払い、$x$ を $2$ 倍する ($x\ =\ 4$)。 - $2$ 枚のコインを支払い、$x$ を $3$ 倍する ($x\ =\ 12$)。 - $8$ 枚のコインを支払い、$x$ を $1$ 減らす ($x\ =\ 11$)。 $2$ 個目のテストケースで、必要な最小枚数である $19$ 枚のコインで目標を達成する方法は以下の通りです。 - はじめ、$x\ =\ 0$ である。 - $8$ 枚のコインを支払い、$x$ を $1$ 増やす ($x\ =\ 1$)。 - $1$ 枚のコインを支払い、$x$ を $2$ 倍する ($x\ =\ 2$)。 - $2$ 枚のコインを支払い、$x$ を $5$ 倍する ($x\ =\ 10$)。 - $8$ 枚のコインを支払い、$x$ を $1$ 増やす ($x\ =\ 11$)。