#include<bits/stdc++.h>

using namespace std;

long long A, B, C, D, N;
const long long INF = 1LL << 60;
unordered_map < long long, long long > mp;

int modul (int x)
{
    if (x < 0)
        return -x;
    return x;
}

long long add (long long a, long long b)
{
    if (a + b > INF)
        return INF;
    return a + b;
}

long long solve (long long N)
{
    if (mp.count (N))
        return mp[N];
    long long best = INF;
    if (N <= INF / D)
        best = 1LL * N * D;
    for (int i=-4; i<=4; i++)
        if (N - i >= 0)
        {
            long long M = N - i, xtra = 1LL * D * modul (i);
            if (M % 2 == 0 && -1 <= i && i <= 1)
            {
                long long curr = add (solve (M / 2), add (A, xtra));
                if (curr < best)
                    best = curr;
            }
            if (M % 3 == 0 && -2 <= i && i <= 2)
            {
                long long curr = add (solve (M / 3), add (B, xtra));
                if (curr < best)
                    best = curr;
            }
            if (M % 5 == 0)
            {
                long long curr = add (solve (M / 5), add (C, xtra));
                if (curr < best)
                    best = curr;
            }
        }
    mp[N] = best;
    return best;
}

long long d[1009];
void update (long long &x, long long y, bool &ok)
{
    if (y < x)
        x = y, ok = 1;
}

const long long opt = 1100000000000000000;
int mx2 = 59, mx3, mx5;

long long mul (long long a, long long b)
{
    if (a > opt / b)
        return opt + 1;
    return 1LL * a * b;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

/*p2[0] = 1;
for (int i=1; i<=mx2; i++)
    p2[i] = p2[i - 1] + p2[i - 1];
p3[0] = 1;
for (int j=1; j<=60; j++)
{
    p3[j] = 3LL * p3[j - 1];
    if (p3[j - 1] > opt / 3)
    {
        mx3 = j - 1;
        break;
    }
}
p5[0] = 1;
for (int j=1; j<=60; j++)
{
    p5[j] = 5LL * p5[j - 1];
    if (p5[j - 1] > opt / 5)
    {
        mx5 = j - 1;
        break;
    }
}
for (int i=0; i<=mx2; i++)
    for (int j=0; j<=mx3; j++)
        for (int k=0; k<=mx5; k++)
            p[i][j][k] = mul (mul (p2[i], p3[j]), p5[k]);*/
int tests;
scanf ("%d", &tests);
while (tests --)
{
    mp.clear ();
    d[0] = 0;
    for (int i=1; i<=300; i++)
        d[i] = INF;
    scanf ("%lld %lld %lld %lld %lld", &N, &A, &B, &C, &D);
    bool ok = 1;
    while (ok)
    {
        ok = 0;
        for (int i=1; i<=300; i++)
        {
            if (i % 2 == 0)
                update (d[i], d[i / 2] + A, ok);
            if (i % 3 == 0)
                update (d[i], d[i / 3] + B, ok);
            if (i % 5 == 0)
                update (d[i], d[i / 5] + C, ok);
            for (int k=0; k<=300; k++)
            {
                int j = k - i;
                update (d[i], d[k] + 1LL * D * modul (j), ok);
            }
        }
    }
    for (int i=0; i<10; i++)
        mp[i] = d[i];
/*    long long best = solve (N);
    for (int i=0; i<=mx2; i++)
        for (int j=0; j<=mx3; j++)
            for (int k=0; k<=mx5; k++)
                if (p[i][j][k] <= opt)
                {

                }*/
    printf ("%lld\n", solve (N));
    //fprintf (stderr, "%d\n", mp.size ());
}
return 0;
}


Measured memory_bytes: 4284