AT_agc044_a [AGC044A] Pay to Win

[problemUrl]: https://atcoder.jp/contests/agc044/tasks/agc044_a あなたは $ 0 $ という数を持っており、これを $ N $ に変えようとしています。 あなたが持っている数は、以下の操作により、定まった枚数のコインを支払うことで変化させることができます。 - $ A $ 枚のコインを支払い、持っている数を $ 2 $ 倍する。 - $ B $ 枚のコインを支払い、持っている数を $ 3 $ 倍する。 - $ C $ 枚のコインを支払い、持っている数を $ 5 $ 倍する。 - $ D $ 枚のコインを支払い、持っている数を $ 1 $ 増やす、または $ 1 $ 減らす。 これらの操作は、任意の順に何度でも行うことができます。 持っている数を $ N $ とするには、最小で何枚のコインが必要でしょうか。 **$ T $ 個のテストケースについて答えてください。**

入力は標準入力から与えられる。入力の $ 1 $ 行目は以下の通りである。 > $ 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 $ はすべて整数である。 ### 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 $)。