#include <bits/stdc++.h>
 
using namespace std;
using LL = long long int; 

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.st <<","<<P.nd <<")";
}

#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

LL n, a, b, c, d;

map<LL, int> memo;
priority_queue<pair<pair<LL, LL>, int>> q;

void toQueue(LL a, LL b, LL c) {
  q.push({{a, b}, c});
}

vector<pair<pair<int, int>, pair<int, LL>>> pre;

void solve() {
  cin >> n >> a >> b >> c >> d;
  memo.clear();

  while (!q.empty()) {
    q.pop();
  }

  LL pot = 1;
  LL mnoz = 2;
  LL res = -1;
  // for (auto x : pre) {
  //   if (abs(x.second.second - n) <= 1000000000) {
  //     LL val = abs(x.second.second - n) * d;
  //     toQueue(-val, x.second.second, 0);
  //     debug(x.second.second);
  //   }
  // }
  // for (int i = 0; i < 60; ++i) {
  //   if (pot * mnoz >= n) {
  //     LL act1 = pot;
  //     LL act2 = pot * mnoz;
  //     toQueue(-(d * (n - act1)), pot * mnoz, 0);
  //     toQueue(-(d * (n - act2)), pot, 0);
  //     break;
  //   }
  // }

  // pot = 1;
  // mnoz = 3;
  // for (int i = 0; i < 38; ++i) {
  //   if (pot * mnoz >= n) {
  //     LL act1 = pot;
  //     LL act2 = pot * mnoz;
  //     toQueue(-(d * (n - act1)), pot * mnoz, 0);
  //     toQueue(-(d * (n - act2)), pot, 0);
  //     break;
  //   }
  // }

  // pot = 1;
  // mnoz = 5;
  // for (int i = 0; i < 26; ++i) {
  //   if (pot * mnoz >= n) {
  //     LL act1 = pot;
  //     LL act2 = pot * mnoz;
  //     toQueue(-(d * (n - act1)), pot * mnoz, 0);
  //     toQueue(-(d * (n - act2)), pot, 0);
  //     break;
  //   }
  // }
  q.push({{0, n}, 0});
  while(!q.empty()) {
    auto xx = q.top();
    LL val = -xx.first.first;
    LL w = xx.first.second;
    LL cnt = xx.second;
    q.pop();
    // debug(val, w, cnt);
    if (w <= 1000000000000000000 / d) {
      if (res == -1) {
        res = w * d + val;
      }
      res = min(res, w * d + val);
    }

    if (memo.count(w)) {
      continue;
    }

    memo[w] = val;
    if (w == 0) {
      if (res == -1) {
        res = val;
      }
      cout << min(val, res) << endl;
      break;  
    }

    if (w % 2 == 0) {
      toQueue(-(val + a), w / 2, cnt);
    }

    if (w % 3 == 0) {
      toQueue(-(val + b), w / 3, cnt);
    }

    if (w % 5 == 0) {
      toQueue(-(val + c), w / 5, cnt);
    }

    if (cnt <= 60) {
      toQueue(-(val + d), w + 1, cnt + 1);
      if (w - 1 >= 0) {
        toQueue(-(val + d), w - 1, cnt + 1);
      }
    }
  }
}
LL INF = 1000000000000000000;

int main() {
  LL act = 1;
  for (int i = 0; i <= 60; ++i) {
    LL oldAct2 = act;
    for (int j = 0; j <= 38; ++j) {
      LL oldAct3 = act;
      for (int k = 0; k <= 26; ++k) {
        pre.push_back({{i, j}, {k, act}});
        if (act >= INF) {
          break;
        }
        act *= 5;
      }
      act = oldAct3;
      if (act >= INF) {
        break;
      }
      act *= 3;
    }
    act = oldAct2;
    act *= 2;
  }
  int z;
  cin >> z;
  while (z--) {
    solve();
  }
}


Measured memory_bytes: 23088