Language: C++

#ifndef Local
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")
#endif

#include <bits/stdc++.h>

#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

#define popCnt(x) (__builtin_popcountll(x))

typedef long long Long;

const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {  // To use most bits rather than just the lowest ones:
  const uint64_t C = Long(4e18 * acos(0)) | 71;  // large odd number
  Long operator()(Long x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
};
__gnu_pbds::gp_hash_table<Long, Long, chash> ht({}, {}, {}, {}, {1 << 16});

Long a, b, c, d;

Long mul(Long x, Long y) {
  if (x > LLONG_MAX / y) return LLONG_MAX;
  return x * y;
}

Long solve(Long x) {
  if (x == 0) return 0;
  if (x == 1) return d;
  if (x == 2) return d + min(a, d);
  auto it = ht.find(x);
  if (it != ht.end()) return it->second;
  Long res = 1e15;
  // 2
  res = min(res, solve(x / 2) + min(a, mul(x / 2, d)) + (x % 2) * d);
  res = min(res, solve((x + 1) / 2) + a + d);
  // 3
  res = min(res, solve(x / 3) + min(b, mul(2 * (x / 3), d)) + (x % 3) * d);
  res = min(res, solve(x / 3 + 1) + b + (3 - (x % 3)) * d);
  // 5
  res = min(res, solve(x / 5) + min(c, mul(4 * (x / 5), d)) + (x % 5) * d);
  res = min(res, solve(x / 5 + 1) + c + (5 - (x % 5)) * d);

  return ht[x] = res;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  int t;
  cin >> t;

  while (t--) {
    Long n;
    cin >> n >> a >> b >> c >> d;
    ht.clear();
    cout << solve(n) << endl;
  }
  return 0;
}

Compiler output:
In file included from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:6:
/usr/include/c++/14/bits/allocator.h: In function 'void __static_initialization_and_destruction_0()':
/usr/include/c++/14/bits/allocator.h:161:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::allocator() noexcept [with _Tp = __gnu_pbds::detail::gp_ht_map<long long int, long long int, chash, std::equal_to<long long int>, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<>, __gnu_pbds::linear_probe_fn<long unsigned int>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<>, __gnu_pbds::hash_load_check_resize_trigger<>, false, long unsigned int> >::entry]': target specific option mismatch
  161 |       allocator() _GLIBCXX_NOTHROW { }
      |       ^~~~~~~~~
In file included from /usr/include/c++/14/ext/pb_ds/detail/container_base_dispatch.hpp:72,
                 from /usr/include/c++/14/ext/pb_ds/assoc_container.hpp:48,
                 from a.cc:9:
/usr/include/c++/14/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp:46:1: note: called from here
   46 | PB_DS_CLASS_C_DEC::s_entry_allocator;
      | ^