#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

typedef long long ll;

const ll M = 2e18;
ll T;
ll n, a, b, c, d;
map<ll, ll> ma;

ll f(ll p)
{
    if(ma[p]) return ma[p];
    if(p == 1) return d;
    if(p == 0) return 0;
    ll re = 4e18;
    re = min(re, a + f(p / 2) + p % 2 * d);
    if(p > 2) re = min(re, a + f(p / 2 + 1) + (2 - p % 2) * d);
    re = min(re, b + f(p / 3) + p % 3 * d);
    re = min(re, b + f(p / 3 + 1) + (3 - p % 3) * d);
    re = min(re, c + f(p / 5) + p % 5 * d);
    re = min(re, c + f(p / 5 + 1) + (5 - p % 5) * d);
    if(M / p >= d) re = min(re, d * p);
    return ma[p] = re;
}

int main()
{
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
        ma.clear();
        printf("%lld\n", f(n));
    }
    return 0;
}
