#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18;

ll N,A,B,C,D;
unordered_map<ll,ll> dp;

ll dfs(ll n){
    if (dp.count(n)) return dp[n];
    if (!n) return 0;
    dp[n]=n>INF/D?INF:D*n;
    dp[n]=min(dp[n],dfs(n/2)+A+n%2*D);
    dp[n]=min(dp[n],dfs((n+1)/2)+A+(2-n%2)%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];
}

void solve(){
    dp.clear();
    cout << dfs(N) << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (;T--;){
        cin >> N >> A >> B >> C >> D;
        solve();
    }
}