配点 : $400$ 点

問題文

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

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

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

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

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

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

制約

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

入力

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

$T$

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

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

出力

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

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$ 個目のテストケースで、必要な最小枚数である $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$)。