A - Pay to Win 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

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

Score : 400 points

Problem Statement

You start with the number 0 and you want to reach the number N.

You can change the number, paying a certain amount of coins, with the following operations:

  • Multiply the number by 2, paying A coins.
  • Multiply the number by 3, paying B coins.
  • Multiply the number by 5, paying C coins.
  • Increase or decrease the number by 1, paying D coins.

You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach N?

You have to solve T testcases.

Constraints

  • 1 \le T \le 10
  • 1 \le N \le 10^{18}
  • 1 \le A, B, C, D \le 10^9
  • All numbers N, A, B, C, D are integers.

Input

The input is given from Standard Input. The first line of the input is

T

Then, T lines follow describing the T testcases. Each of the T lines has the format

N A B C D

Output

For each testcase, print the answer on Standard Output followed by a newline.

Sample Input 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

Sample Output 1

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:

  • Initially x = 0.
  • Pay 8 to increase by 1 (x = 1).
  • Pay 1 to multiply by 2 (x = 2).
  • Pay 1 to multiply by 2 (x = 4).
  • Pay 2 to multiply by 3 (x = 12).
  • Pay 8 to decrease by 1 (x = 11).

For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:

  • Initially x = 0.
  • Pay 8 to increase by 1 (x = 1).
  • Pay 1 to multiply by 2 (x = 2).
  • Pay 2 to multiply by 5 (x = 10).
  • Pay 8 to increase by 1 (x = 11).