#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using pll = pair<ll, ll>;
const ll inf = 1LL << 60;

// {0, positive, 1 negative }

ll n, a, b, c, d;
bool visited[61][41][31];
ll memo[61][41][31][2];

inline ll add(ll a, ll b) {
	if(a + b >= inf) {
		return inf;
	} else {
		return a + b;
	}
}


inline ll mul(ll a, ll b) {
	if (a == 0 or b == 0) return 0LL;

	if(a >= inf / b) {
		return inf;
	} else {
		return a * b;
	}
}

ll calc(ll ca, ll cb, ll cc) {
	ll ret = 1LL;
	rep(loop, ca) ret = mul(ret, 2LL);
	rep(loop, cb) ret = mul(ret, 3LL);
	rep(loop, cc) ret = mul(ret, 5LL);
	return ret;
}

#define error(args...) { vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c){
	vector<string> v;stringstream ss(s);string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a,Args... args){
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ",err(++it, args...);
}


void solve(ll ca, ll cb, ll cc) {
	if (visited[ca][cb][cc]) return;
	visited[ca][cb][cc] = true;

	memo[ca][cb][cc][0] = inf;
	memo[ca][cb][cc][1] = inf;
	const ll coef = calc(ca, cb, cc);

	if(coef >= inf) {
		return;
	}

	const ll to[2] = {n % coef, n % coef - coef};
	rep(ti, 2) {
		const ll cost = mul(d, abs(n - to[ti]) / coef);
		chmin(memo[ca][cb][cc][ti], cost);
	}


	{
		const ll ncoef = calc(ca + 1, cb, cc);
		const ll from[2] = {n % ncoef, n % ncoef - ncoef};
		solve(ca + 1, cb, cc);
		rep(fi, 2) rep(ti, 2) {
			const ll cost = a + mul(d, abs(to[ti] - from[fi]) / coef);
			const ll nval = add(memo[ca + 1][cb][cc][fi], cost);
			chmin(memo[ca][cb][cc][ti], nval);
		}
	}

	{
		const ll ncoef = calc(ca, cb + 1, cc);
		const ll from[2] = {n % ncoef, n % ncoef - ncoef};
		solve(ca, cb + 1, cc);
		rep(fi, 2) rep(ti, 2) {
			const ll cost = b + mul(d, abs(to[ti] - from[fi]) / coef);
			const ll nval = add(memo[ca][cb + 1][cc][fi], cost);
			chmin(memo[ca][cb][cc][ti], nval);
		}
	}

	{
		const ll ncoef = calc(ca, cb, cc + 1);
		const ll from[2] = {n % ncoef, n % ncoef - ncoef};
		solve(ca, cb, cc + 1);
		rep(fi, 2) rep(ti, 2) {
			const ll cost = c + mul(d, abs(to[ti] - from[fi]) / coef);
			const ll nval = add(memo[ca][cb][cc + 1][fi], cost);
			chmin(memo[ca][cb][cc][ti], nval);
		}
	}
}

int main(void){
	int t;
	cin >> t;

	rep(loop, t) {
		cin >> n >> a >> b >> c >> d;
		rep(i, 61) rep(j, 41) rep(k, 31) visited[i][j][k] = false;
		solve(0, 0, 0);
		cout << memo[0][0][0][0] << endl;
	}

	return 0;
}

Measured memory_bytes: 4496