/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (win, osx, linux)
 * Author: step_by_step
 * Time: 2020-03-19 17:35:03
**/

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

int main()
{
    //freopen("circus.in", "r", stdin);
    //freopen("circus.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int T;
    cin >> T;
    while (T--) {
        ll n, A, B, C, D;
        cin >> n >> A >> B >> C >> D;
        ll ans = big;
        if (D <= big / n) {
            setmin(ans, n * D);
        }
        map<ll, ll> mapa;
        mapa[n] = 0;
        ll cur_v = n;
        auto upd_val = [&](ll x, ll dist) {
            if (!mapa.count(x)) {
                mapa[x] = dist;
            } else {
                mapa[x] = min(mapa[x], dist);
            }
            rep(d, -4, 4 + 1) {
                if (mapa.count(x + d)) {
                    mapa[x + d] = min(mapa[x + d], dist + D * abs(d));
                }
            }
        };
        while (cur_v >= 1) {
            auto it = --mapa.upper_bound(cur_v);
            ll v = it->fi, d = it->se;
            if (D <= big / v) {
                setmin(ans, d + v * D);
            }
            if (v == 1) {
                break;
            }
            cur_v = v - 1;
            if (v % 2 == 0) {
                upd_val(v / 2, d + A);
            } else {
                upd_val((v + 1) / 2, d + D + A);
                if ((v - 1) / 2 > 0) {
                    upd_val((v - 1) / 2, d + D + A);
                }
            }
            if (v % 3 == 0) {
                upd_val(v / 3, d + B);
            } else {
                int r = v % 3;
                if (v - r > 0) {
                    upd_val((v - r) / 3, d + D * r + B);
                }
                upd_val((v + 3 - r) / 3, d + D * (3 - r) + B);
            }
            if (v % 5 == 0) {
                upd_val(v / 5, d + C);
            } else {
                int r = v % 5;
                if (v - r > 0) {
                    upd_val((v - r) / 5, d + D * r + C);
                }
                upd_val((v + 5 - r) / 5, d + D * (5 - r) + C);
            }
        }
        /*for (auto it : mapa) {
            cout << it.fi << " " << it.se << "\n";
        }*/
        cout << ans << "\n";
    }
    return 0;
}



Measured memory_bytes: 4408