#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
map<long long, long long> dp;
long long a, b, c, d;
long long dfs(long long n) {
  if (n == 0) return 0;
  if (dp.count(n)) return dp[n];
  if (n > 4e18 / d)
    dp[n] = 4e18;
  else
    dp[n] = n * d;
  dp[n] = min(dp[n], dfs(n / 2) + a + n % 2 * d);
  dp[n] = min(dp[n], dfs((n + 1) / 2) + a + n % 2 * d);
  dp[n] = min(dp[n], dfs(n / 3) + b + n % 3 * d);
  dp[n] = min(dp[n], dfs((n + 2) / 3) + b + (3 - n % 3) % 3 * d);
  dp[n] = min(dp[n], dfs(n / 5) + c + n % 5 * d);
  dp[n] = min(dp[n], dfs((n + 4) / 5) + c + (5 - n % 5) % 5 * d);
  return dp[n];
}
int main() {
  long long T;
  scanf("%lld", &T);
  while (T--) {
    dp.clear();
    long long n;
    scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
    printf("%lld\n", dfs(n));
  }
  return 0;
}
