#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <string>

#include <vector>

#include <bits/stdc++.h>

using namespace std;

 

//priority_queue<long long, vector<long long>, greater<long long>> pq;



const double TL = 1.5 * CLOCKS_PER_SEC;

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

#define clr(x, y) memset(x, y, sizeof(x))

#define forn(i, n) for (int i = 0; i < n; i++)

#define LL long long

const double pi = acos(-1.0);





LL n, a, b, c, d;

map<LL, LL> mp;



LL mul(LL x, LL y) {

  if (x > 1e16 / y) return 1e16;

  return x * y;

}

//LL mul(LL x, LL y) {

//  LL ret = x * y;

//  if (ret / y != x) return 1e16;

//  if (ret > 1e16) return 1e16;

//  return ret;

//}





LL dfs(LL x) {

  if (x == 0) {

    return 0;

  }

  if (x == 1) {

    return d;

  }

  if (mp.find(x) != mp.end()) {

    return mp[x];

  }

  //cout << x << endl;





  LL ans = 1e16;

  LL y = x % 2;

  LL z = (x - y) / 2;

  ans = min(ans, dfs(z) + min(d * y + a, mul(abs(z - x), d)));

  if (y != 0) {

    z += 1;

    ans = min(ans, dfs(z) + min(d * (2 - y) + a, mul(abs(z - x), d)));

  }





  y = x % 3;

  z = (x - y) / 3;

  ans = min(ans, dfs(z) + min(d * y + b, mul(abs(z - x), d)));

  if (y != 0) {

    z += 1;

    ans = min(ans, dfs(z) + min(d * (3 - y) + b, mul(abs(z - x), d)));

  }



  y = x % 5;

  z = (x - y) / 5;

  ans = min(ans, dfs(z) + min(d * y + c, mul(abs(z - x), d)));

  if (y != 0) {

    z += 1;

    ans = min(ans, dfs(z) + min(d * (5 - y) + c, mul(abs(z - x), d)));

  }



  mp[x] = ans;

  return ans;

}



int main() {

#ifdef LOCAL

  auto start_clock = clock();

  freopen("in", "r", stdin);

#endif

  int T;

  scanf("%d", &T);

  while (T--) { 

    mp.clear();

    cin >> n >> a >> b >> c >> d;

    cout << dfs(n) << endl;

  }



#ifdef LOCAL

 auto end_clock = clock();

 cout << "Time:" << (end_clock - start_clock) / CLOCKS_PER_SEC << endl;

#endif

  return 0;

}

