//
// AGC044A
// URL : https://atcoder.jp/contests/agc044/tasks/agc044_a
// 
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;

namespace AtCoder
{
    class AGC044A
    {
        public static readonly long MOD_CONST = 1000000007;//(long)Math.Pow(10, 9) + 7;

        static void Main(string[] args)
        {
            //出力高速化
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }
        //メモ
        //<long, long> = <引数n, 持っている数をnにするために支払う必要がある最小のコイン枚数>
        public static Dictionary<long, long> memo = new Dictionary<long, long>();
        public static long N;
        public static long A;
        public static long B;
        public static long C;
        public static long D;

        public static void Solve()
        {
            int T = int.Parse(Console.ReadLine());

            var ans = new long[T];
            for (int i = 0; i < T; ++i)
            {
                long[] inputLongArray = Console.ReadLine().Split(' ').Select(_inputStr => long.Parse(_inputStr)).ToArray();
                N = inputLongArray[0];
                A = inputLongArray[1];
                B = inputLongArray[2];
                C = inputLongArray[3];
                D = inputLongArray[4];
                memo.Clear();
                ans[i] = DP(N);
            }
            foreach(var a in ans){
                Console.WriteLine(a);
            }
        }

        /// <summary>
        /// 与えられた数nにするための最小のコイン枚数を計算する
        /// </summary>
        /// <param name="N">目標値</param>
        /// <returns></returns>
        public static long DP(long n)
        {
            //例外対策
            if(n == 0) { return 0; }
            if(n == 1) { return D; }//D支払って+1するしか道がない

            //メモから取り出して、計算を省略する
            if(memo.TryGetValue(n, out var coin_indic) == true)
            {
                return coin_indic;
            }
            var coin = long.MaxValue;

            //p={2,3,5}として、nに一番近いpの倍数をgとして
            //D * abs(n - g) * pのコスト
            //とすると、最小コストで数を小さくできる
            //次にgにするための最小コストを計算する(DP()の部分、つまり再帰)

            coin = Math.Min(coin, D * Math.Abs(n - divFloor(n, 5) * 5) + C + DP(divFloor(n, 5)));
            coin = Math.Min(coin, D * Math.Abs(n - divCeil(n, 5)  * 5) + C + DP(divCeil(n, 5)));

            coin = Math.Min(coin, D * Math.Abs(n - divFloor(n, 3) * 3) + B + DP(divFloor(n, 3)));
            coin = Math.Min(coin, D * Math.Abs(n - divCeil(n, 3)  * 3) + B + DP(divCeil(n, 3)));

            coin = Math.Min(coin, D * Math.Abs(n - divFloor(n, 2) * 2) + A + DP(divFloor(n, 2)));
            coin = Math.Min(coin, D * Math.Abs(n - divCeil(n, 2)  * 2) + A + DP(divCeil(n, 2)));

            //コストDで+-1だけし続ける場合
            if (long.MaxValue / n > D)//桁の最大値を超えない場合だけ処理する
            {
                coin = Math.Min(coin, D * n);
            }

            memo.Add(n, coin);
            return coin;
        }

        /// <summary>
        /// floor(a/b)
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static long divFloor(long a, long b)
        {
            return a / b;
        }
        /// <summary>
        /// ceil(a/b) a,bが整数だと途中で小数点以下が削られるが、それも対策したやつ
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static long divCeil(long a, long b)
        {
            return (a + b - 1) / b;
        }



        //---------------------------------------------------------------------------------
        #region MyLib

        /// <summary>
        /// Clamping
        /// </summary>
        /// <typeparam name="T">比較型</typeparam>
        /// <param name="x">clampしたい値</param>
        /// <param name="min">最小値</param>
        /// <param name="max">最大値</param>
        /// <returns>clamp済みの値</returns>
        public static T Clamp<T>(T x, T min, T max) where T : IComparable<T>
        {
            if (x.CompareTo(min) < 0) { return min; }
            else if (x.CompareTo(max) > 0) { return max; }
            else return x;
            //return Math.Max(Math.Min(x, max), min);
        }

        /// <summary>
        /// 指定された底log_baseでの, 対数を計算
        /// </summary>
        /// <param name="x"></param>
        /// <param name="log_base">指定の底</param>
        /// <returns></returns>
        public static double LogBase(double x, double log_base)
        {
            //log_b(N) = log_a(N) / log_a(B)より
            return Math.Log(x) / Math.Log(log_base);
        }

        /// <summary>
        /// 初項a, 公差d, 項数nの数列の和
        /// </summary>
        /// <param name="n">求めたいところ</param>
        /// <returns>初項からxまで足した値</returns>
        static long SumSeries(long a, long d, long n)
        {
            return (2 * a + (n - 1) * d) * n / 2;
        }
        /// <summary>
        /// 累積和の配列を計算する
        /// Sum[ a[0], a[i] )がs[i+1]に入っている
        /// s[0]  : 0                //一切和を取らない場合
        /// s[1]  : ls[0]            //a[0]   + s[0] = a[0]
        /// s[2]  : ls[1] + s[1]     //a[1]   + a[0]
        /// ...
        /// s[N]  : ls[N-1] + s[N-1] //a[N-1] + ... + a[0]
        /// s[N+1]: ls[N] + s[N]     //a[N]   + ... + a[0]
        /// 
        /// 例: [1, 7)の和(a[1] + ... + a[6])
        /// s[1] = a[0] //[0, 1)
        /// s[7] = a[0] + a[1] + ... + a[6] //[0, 7)
        /// よってs[7] - s[1]);
        /// </summary>
        /// <param name="ls">計算したい配列</param>
        /// <returns>累積和配列</returns>
        static List<long> AggregateSumList(List<long> a)
        {
            var s = new List<long>(a.Count + 1);
            if (a.Count == 0)
            {
                return s;
            }
            s.Add(0);//s[0] = 0
            for (int i = 0; i < a.Count; ++i)
            {
                s.Add(a[i] + s[i]);
            }
            return s;
        }


        /// <summary>
        /// 与えられた数が素数かどうかを計算する
        /// </summary>
        /// <param name="num">対象数</param>
        /// <returns>true:素数, false:素数ではない(合成数)</returns>
        public static bool isPrime(int num)
        {
            if (num < 2) return false;
            else if (num == 2) return true;
            else if (num % 2 == 0) return false;

            double sqrtNum = Math.Sqrt(num);
            for (int i = 3; i <= sqrtNum; i += 2)
            {
                if (num % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 順列mPnを計算する
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long Permutation(long m, long n)
        {
            long ret = 1;
            for (var i = 0; i < n; ++i)
            {
                ret *= m - i;
            }
            return ret;
        }
        /// <summary>
        /// 組み合わせmCnを計算する
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long Combination(long m, long n)
        {
            if (m == n || n == 0)
            {
                return 1;
            }
            long ans = 1;
            for (var i = 1; i <= n; ++i)
            {
                ans = ans * (m - i + 1) / i;
            }
            return ans;
        }

        static long Gcd(long m, long n)
        {
            if (n == 0) return m;
            return Gcd(n, m % n);
        }

        static long Lcm(long m, long n)
        {
            var gcd = Gcd(m, n);
            //return (m * n) / gcd;
            return m / gcd * n;//桁あふれ対策
        }
        #endregion MyLib
    }
}



Measured memory_bytes: 28668