#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const ll mod=998244353;

map<ll,ll>dp;
ll a,b,c,d;

ll dfs(ll n)
{
    if(n==0)return 0;
    if(dp.count(n))return dp[n];
    if(n>4e18/d)dp[n]=4e18;
    else dp[n]=n*d;
    dp[n]=min(dp[n],dfs(n/2)+a+n%2*d);
    dp[n]=min(dp[n],dfs((n+1)/2)+a+n%2*d);
    dp[n]=min(dp[n],dfs(n/3)+b+n%3*d);
    dp[n]=min(dp[n],dfs((n+2)/3)+b+(3-n%3)%3*d);
    dp[n]=min(dp[n],dfs(n/5)+c+n%5*d);
    dp[n]=min(dp[n],dfs((n+4)/5)+c+(5-n%5)%5*d);
    return dp[n];
}

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