#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<functional>
#include<numeric>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
using namespace std;
typedef long long LL;
mt19937 gene(233);
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char GET_CHAR(){
	const int maxn = 131072;
	static char buf[maxn],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
inline int getInt() {
	int res(0);
	char c = getchar();
	while(c < '0') c = getchar();
	while(c >= '0') {
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return res;
}

inline int fastpo(int x, int n, int mod) {
	int res(1);
	while(n) {
		if(n & 1) {
			res = res * (LL)x % mod;
		}
		x = x * (LL) x % mod;
		n /= 2;
	}
	return res;
}

inline string itoa(int x, int width = 0) {
  string res;
  if(x == 0) res.push_back('0');
  while(x) {
    res.push_back('0' + x % 10);
    x /= 10;
  }
  while((int)res.size() < width) res.push_back('0');
  reverse(res.begin(), res.end());
  return res;
}

const int N = 1000033;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
LL n, a, b, c, d;
map<LL, LL> mp;
vector<pair<int, int> > e[N];
LL dis[N];
void dp(LL n) {
	if(n == 0) return;
	if(mp.count(n)) return;
	mp[n] = 0;
	/*for(LL m = n - 4; m <= n + 4; m++) {
		if(m % 2 == 0) dp(m / 2);
		if(m % 3 == 0) dp(m / 3);
		if(m % 5 == 0) dp(m / 5);
	}*/
	dp(n / 2);
	dp(n / 3);
	dp(n / 5);
}
int main() {
	int t;
	scanf("%d", &t);
	for(int qq = 1; qq <= t; qq++) {
		cin >> n >> a >> b >> c >> d;
		mp.clear();
		dp(n);
		int np = 0;
		static LL vec[N];
		vec[np++] = 0;
		//cout << mp.size() << endl;
		for(auto itr = mp.begin(); itr != mp.end(); itr++) {
			for(int i = -4; i <= 4; i++) vec[np++] = itr->first + i;
		}
		sort(vec, vec + np);
		np = unique(vec, vec + np) - vec;
		vec[np] = -10000000000000ll;
		int strt, ed;
		priority_queue<pair<LL, int> > pq;
		fill(dis + 1, dis + 1 + np, inf * (LL)inf);
		
		for(int i = 0; i < np; i++) {
			if(vec[i] == 0) strt = i;
			if(vec[i] == n) ed = i;
			dis[i] = (inf) * (LL)inf / d < abs(vec[i]) ? inf * (LL)inf : abs(vec[i]) * (LL)d;
//			if(dis[i] < 0) cout << i << ' ' << dis[i] << endl;
			pq.push(make_pair(-dis[i], i));
			LL x = vec[i];
			int ix = i;
			LL y = x * 2;
			int iy;
			LL * itr = lower_bound(vec, vec + np, y); 
			if(*itr == y) {
				iy = itr - vec;
				e[ix].push_back({iy, a});
			}
			y = x * 3;
			itr = lower_bound(vec, vec + np, y);
			if(*itr == y) {
				iy = itr - vec;
				e[ix].push_back({iy, b});
			}
			y = x * 5;
			itr = lower_bound(vec, vec + np, y);
			if(*itr == y) {
				iy = itr - vec;
				e[ix].push_back({iy, c});
			}
			y = x + 1;
			itr = lower_bound(vec, vec + np, y);
			if(*itr == y) {
				iy = itr - vec;
				e[ix].push_back({iy, d});
			}
			y = x - 1;
			itr = lower_bound(vec, vec + np, y);
			if(*itr == y) {
				iy = itr - vec;
				e[ix].push_back({iy, d});
			}
			
		}
		
		for(;;) {
			while(!pq.empty() && dis[pq.top().second] != -pq.top().first) pq.pop();
			if(pq.empty()) break;
			int v = pq.top().second;
			//cout << v << ' ' << dis[v] << endl;
			pq.pop();
			for(auto tmp : e[v]) {
				int y = tmp.fi, z = tmp.se;
				if(dis[y] > dis[v] + z) {
					dis[y] = dis[v] + z;
					pq.push(make_pair(-dis[y], y));
				}
			}
		}
		cout << dis[ed] << endl;
		for(int i = 1; i <= np; i++) e[i].clear();
	}
}




Measured memory_bytes: 32768