#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pr pair<ll, ll>
#define infinity (ll)4e18
#define maxpossible 9223372036854775807
#define tp tuple<ll, ll, ll>
using namespace std;
long long int mod = 1e9 + 7;

ll solve(ll a, ll b, ll c, ll d, ll n, map<ll, ll> &mp)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return d;
    if (mp.find(n) != mp.end())
        return mp.find(n)->second;
    ll val = infinity;
    if (n % 2 == 0)
    {
        val = min(val, a + solve(a, b, c, d, n / 2, mp));

        if (d * n / 2 < a && d * n / 2 >= 0)
            val = min(val, d * n / 2 + solve(a, b, c, d, n / 2, mp));
    }
    else
    {
        val = min(val, a + d + solve(a, b, c, d, (n + 1) / 2, mp));
        val = min(val, a + d + solve(a, b, c, d, (n - 1) / 2, mp));

        if (d * (n + 1) / 2 < a && d * (n + 1) / 2 >= 0)
            val = min(val, d * (n + 1) / 2 + d + solve(a, b, c, d, (n + 1) / 2, mp));

        if (d * (n - 1) / 2 < a && d * (n - 1) / 2 >= 0)
            val = min(val, d * (n - 1) / 2 + d + solve(a, b, c, d, (n - 1) / 2, mp));
    }
    if (n % 3 == 0)
    {
        val = min(val, b + solve(a, b, c, d, n / 3, mp));

        if (d * 2 * n / 3 < b && d * 2 * n / 3 >= 0)
            val = min(val, d * 2 * n / 3 + solve(a, b, c, d, n / 3, mp));
    }
    else if (n % 3 == 1)
    {
        val = min(val, b + d + solve(a, b, c, d, (n - 1) / 3, mp));
        val = min(val, b + 2 * d + solve(a, b, c, d, (n + 2) / 3, mp));

        if (d * 2 * (n - 1) / 3 < b && d * 2 * (n - 1) / 3 >= 0)
            val = min(val, d * 2 * (n - 1) / 3 + d + solve(a, b, c, d, (n - 1) / 3, mp));

        if (d * 2 * (n + 2) / 3 < b && d * 2 * (n + 2) / 3 >= 0)
            val = min(val, d * 2 * (n + 2) / 3 + 2 * d + solve(a, b, c, d, (n + 2) / 3, mp));
    }
    else
    {
        val = min(val, b + d + solve(a, b, c, d, (n + 1) / 3, mp));
        val = min(val, b + 2 * d + solve(a, b, c, d, (n - 2) / 3, mp));

        if (d * 2 * (n + 1) / 3 < b && d * 2 * (n + 1) / 3 >= 0)
            val = min(val, d * 2 * (n + 1) / 3 + d + solve(a, b, c, d, (n + 1) / 3, mp));

        if (d * 2 * (n - 2) / 3 < b && d * 2 * (n - 2) / 3 >= 0)
            val = min(val, d * 2 * (n - 2) / 3 + 2 * d + solve(a, b, c, d, (n - 2) / 3, mp));
    }
    if (n % 5 == 0)
    {
        val = min(val, c + solve(a, b, c, d, n / 5, mp));

        if (d * 4 * n / 5 < c && d * 4 * n / 5 >= 0)
            val = min(val, d * 4 * n / 5 + solve(a, b, c, d, n / 5, mp));
    }
    for (ll i = 1; i < 5; i++)
    {
        if (n % 5 == i)
        {
            val = min(val, c + i * d + solve(a, b, c, d, (n - i) / 5, mp));
            val = min(val, c + (5 - i) * d + solve(a, b, c, d, (n + 5 - i) / 5, mp));
            if (d * 4 * (n - i) / 5 < c && d * 4 * (n - i) / 5 >= 0)
                val = min(val, d * 4 * (n - i) / 5 + i * d + solve(a, b, c, d, (n - i) / 5, mp));

            if (d * 4 * (n + 5 - i) / 5 < c && d * 4 * (n + 5 - i) / 5 >= 0)
                val = min(val, d * 4 * (n + 5 - i) / 5 + (5 - i) * d + solve(a, b, c, d, (n + 5 - i) / 5, mp));
        }
    }
    mp.emplace(n, val);
    return val;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t;
    cin >> t;
    while (t--)
    {
        ll n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        map<ll, ll> mp;
        cout << solve(a, b, c, d, n, mp) << endl;
    }
    return 0;
}


Measured memory_bytes: 4448