#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define ll long long
ll n,a,b,c,d;
map<ll,ll>dp;
ll inf= 1000000000000000000LL;
ll dfs(ll x)
{
    if(x==0)return 0;
    ll res=inf;
    if(dp.find(x)!=dp.end())
        return dp[x];
    if(x<inf/d)
        res=x*d;
    for(int i=-4;i<=4;i++)
    {
        ll y=x+i;
        if(y%2==0&&abs(i)<2&&y/2<x&&y>=2)res=min(res,dfs(y/2)+a+d*abs(i));
        if(y%3==0&&abs(i)<3&&y/3<x&&y>=3)res=min(res,dfs(y/3)+b+d*abs(i));
        if(y%5==0&&y/5<x&&y>=5)res=min(res,dfs(y/5)+c+d*abs(i));
    }
    return dp[x]=res;
}
void solve()
{
    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
    printf("%lld\n",dfs(n));
}
int main()
{
    int t;
    cin>>t;
    while(t--) {
        dp.clear();
        solve();
    }
}