#include <bits/stdc++.h>
#define P pair<long long, long long>

using namespace std;
const long long INF = 2e18;


int main(){
  int t;
  cin >> t;
  for(int tt=0;tt<t;tt++){
    long long n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    vector<P> v;
    v.clear();
    v.emplace_back(P(2, a));
    v.emplace_back(P(3, b));
    v.emplace_back(P(5, c));
    map<long long, long long> m;
    m[0] = 0;
    m[1] = d;
    function<long long(long long)> dfs = [&](long long x){
      if(m.find(x)!=m.end())return m[x];
      long long ret=INF;
      if((long double)d * (long double)x<ret)ret=d*x;
      for(auto &p: v){
        long long num=p.first;
        long long cost=p.second;
        ret = min(ret, dfs(x/num)+cost+d*(x%num));
        if(x%num!=0){
          ret = min(ret, dfs(x/num + 1)+cost+d*(num-x%num));
        }
    }
    return m[x] = ret;
    };
    cout << dfs(n) << endl;
  }
}

