# include <bits/stdc++.h>
using namespace std;
# define ll long long

ll dvs[] = {2,3,5};
ll cost[3], d, n;
unordered_map<ll, ll> dp;

ll solve(ll x){
  if(x <= 1) return x*d;
  if(dp.count(x)) return dp[x];

  ll res = LLONG_MAX;
  if(x < res/d) res = x*d;

  for(int i=0; i<3; i++){
    ll bwh = (x/dvs[i])*dvs[i];
    ll atas = ((x+dvs[i]-1)/dvs[i])*dvs[i];
    res = min(res, abs(x-bwh)*d + cost[i] + solve(bwh/dvs[i]));
    res = min(res, abs(x-atas)*d + cost[i] + solve(atas/dvs[i]));
  }
  return dp[x] = res;
}

int main(){

  ios_base :: sync_with_stdio(false);

  int T;
  cin >> T;
  while(T--){
    cin >> n;
    for(int i=0; i<3; i++) cin >> cost[i];
    cin >> d;
    dp.clear();
    cout << solve(n) << endl;
  }
  return 0;
}