#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,a,b,c,d;
map<int,int> cc;
int chg(int x)
{
    if(x==0) return 0;
    if(x==1) return d;
    if(cc[x]) return cc[x];
    int res = 1e18;
    if(x<res/d) res = x*d;
    res = min(res,chg(x/2) + (x%2)*d + a);
    if(x>2&&x%2)res = min(res,chg(x/2+1) + (2 - x%2) * d + a);
    if(x%3<2)res = min(res,chg(x/3) + (x%3)*d + b);
    if(x%3>1&&x>1)res = min(res,chg(x/3+1) + (3 - x%3) * d + b);
    if(x%5<3)res = min(res,chg(x/5) + (x%5)*d + c);
    if(x%5>2&&x>1)res = min(res,chg(x/5+1) + (5 - x%5) * d + c);
    cc[x] = res;
    return res;
}
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        cc.clear();
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
        printf("%lld\n",chg(n));
    }
    return 0;
}