#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
#include <math.h>
#include <fstream>

using namespace std;

long long mod = 1000000007;

long long gcd(long long a, long long b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}

long long binpow(long long x, long long k)
{
    if (k == 0)
    {
        return 1LL;
    }
    long long temp = binpow(x, k / 2);
    if (k % 2 == 1)
    {
        return (((temp * temp) % mod) * x) % mod;
    }
    else
    {
        return (temp * temp) % mod;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cin.tie();
    cout.tie();
    // ifstream cin("in.txt");
    // ofstream cout("out.txt");
    
    
    int t;
    cin >> t;
    for (int qwe = 0; qwe < t; qwe++)
    {
        // cout << "Case #" << qwe + 1 << ": ";
        long long n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        set<long long> st;
        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
        pq.push({ 0, n });
        long long rez = 1000000000000000000LL;
        while (!pq.empty())
        {
            pair<long long, long long> curr = pq.top();
            pq.pop();
            if (st.find(curr.second) != st.end())
            {
                continue;
            }
            st.insert(curr.second);
            if (curr.first + 1.0 * curr.second * d <= 1000000000000000000LL)
            {
                rez = min(rez, curr.first + curr.second * d);
            }
            if (curr.second == 1)
            {
                break;
            }
            if (curr.second % 2 == 0)
            {
                pq.push({ curr.first + a, curr.second / 2 });
            }
            else
            {
                pq.push({ curr.first + a + d, (curr.second - 1) / 2 });
                pq.push({ curr.first + a + d, (curr.second + 1) / 2 });
            }

            if (curr.second % 3 == 0)
            {
                pq.push({ curr.first + b, curr.second / 3 });
            }
            else if (curr.second % 3 == 1)
            {
                pq.push({ curr.first + b + d, (curr.second - 1) / 3 });
            }
            else
            {
                pq.push({ curr.first + b + d, (curr.second + 1) / 3 });
            }

            if (curr.second % 5 == 0)
            {
                pq.push({ curr.first + c, curr.second / 5 });
            }
            else if (curr.second % 5 == 1)
            {
                pq.push({ curr.first + c + d, (curr.second - 1) / 5 });
            }
            else if (curr.second % 5 == 2)
            {
                pq.push({ curr.first + c + 2 * d, (curr.second - 2) / 5 });
            }
            else if (curr.second % 5 == 3)
            {
                pq.push({ curr.first + c + 2 * d, (curr.second + 2) / 5 });
            }
            else if (curr.second % 5 == 4)
            {
                pq.push({ curr.first + c + d, (curr.second + 1) / 5 });
            }
        }
        cout << rez << '\n';
    }


    return 0;
}


Measured memory_bytes: 4036