#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  int t;
  cin >> t;
  while (t--) {
    long long n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    if (n == 0) {
      cout << 0 << '\n';
    } else if (n == 1) {
      cout << d << '\n';
    } else {
      if (n <= 30) {
        long long dp[n + 6];
        dp[0] = 0;
        dp[1] = d;
        for (long long i = 2; i <= n + 5; i++) {
          dp[i] = dp[i - 1] + d;
          if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + a);
          }
          if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + b);
          }
          if (i % 5 == 0) {
            dp[i] = min(dp[i], dp[i / 5] + c);
          }
        }
        cout << dp[n] << '\n';
      } else {
        long long dp[36];
        dp[0] = 0;
        dp[1] = d;
        for (long long i = 2; i <= 35; i++) {
          dp[i] = dp[i - 1] + d;
          if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + a);
          }
          if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + b);
          }
          if (i % 5 == 0) {
            dp[i] = min(dp[i], dp[i / 5] + c);
          }
        }
        long long ans = dp[100];
        n -= 100;
        long long A[3];
        A[0] = (long long)n / 2 * a;
        A[1] = (long long)n / 3 * b;
        A[2] = (long long)n / 5 * c;
        sort(A, A + 3);
        ans += A[0];
        cout << ans << '\n';
      }
    }
  }
  return 0;
}
