//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro

ll n,a,b,c,d;

priority_queue<pair<pll,pll> >pq; // dist+heuristic, dist, now, 1walks
set<ll>vis[15];
// if same dist, prioritize lower number

ll cost1(ll x){
	ll dist = x;
	return x;

	if(dist > INF / d){
		dist = INF;
	}else{
		dist *= d;
	}
	return dist;
}

ll cost1(ll a, ll b){
	ll dist = abs(a-b);

	if(dist > INF / d){
		dist = INF;
	}else{
		dist *= d;
	}
	return dist;
}

ll geth(ll x){
	return 0;
	// expected from x to n
	ll dist = cost1(x);

	// muls
	if(x != 0){
		ll now, cs;
		now = x;
		cs = 0;
		while(now){
			if(now % 2 == 0){
				now /= 2;
				cs += min(a, cost1(now, now/2));
			}else{
				now--;
				cs += d;
			}
		}
		dist = min(dist, cs);
		now = x;
		cs = 0;
		while(now){
			if(now % 3 == 0){
				now /= 3;
				cs += min(b, cost1(now, now/2));
			}else{
				now--;
				cs += d;
			}
		}
		dist = min(dist, cs);
		now = x;
		cs = 0;
		while(now){
			if(now % 5 == 0){
				now /= 5;
				cs += min(c, cost1(now, now/2));
			}else{
				now--;
				cs += d;
			}
		}
		dist = min(dist, cs);

	}

	return dist;
}

ll safeadd(ll a, ll b){
	if(a + b > INF)return INF;
	return a+b;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);

    int t;
    cin>>t;
    while(t--){
	    cin>>n>>a>>b>>c>>d;
	    while(!pq.empty())pq.pop();
	    FOR(i,15)vis[i].clear();

	    pq.push({{-geth(0), -n}, {0, 0}});
	    ll ans = -1;
	    while(!pq.empty()){
	    	ll heur = -pq.top().F.F;
	    	ll dist = -pq.top().S.F;
	    	ll now = -pq.top().F.S;
	    	ll walks = pq.top().S.S;
	    	pq.pop();

	    	if(vis[walks].count(now))continue;
	    	vis[walks].insert(now);

	    	// printf("now %lld, dist %lld, heur %lld\n",now,dist,heur);

	    	if(now == 0){
	    		ans = dist;
	    		break;
	    	}

	    	ll to, nd;
	    	if(now % 2 == 0){
		    	// mul2
		    	to = now / 2;
		    	nd = safeadd(dist, min(a, cost1(now, to)));
		    	pq.push({{-safeadd(nd, geth(to)), -to}, {-nd, 0}});
		    }

		    if(now % 3 == 0){
		    	// mul3
		    	to = now / 3;
		    	nd = safeadd(dist, min(b, cost1(now, to)));
		    	pq.push({{-safeadd(nd, geth(to)), -to}, {-nd, 0}});
		    }

		    if(now % 5 == 0){
		    	// mul5
		    	to = now / 5;
		    	nd = safeadd(dist, min(c, cost1(now, to)));
		    	pq.push({{-safeadd(nd, geth(to)), -to}, {-nd, 0}});
	    	}

	    	// sub1
	    	if(walks < 5){
		    	if(now > 0){
		    		to = now-1;
		    		nd = safeadd(dist, d);
			    	pq.push({{-safeadd(nd, geth(to)), -to}, {-nd, walks+1}});
		    	}

		    	// add1
		    	to = now+1;
		    	nd = safeadd(dist, d);
			    pq.push({{-safeadd(nd, geth(to)), -to}, {-nd, walks+1}});

	    	}


	    	// ll add = 1;
	    	// ll cost = d;
	    	// while(now - add >= 0){
	    	// 	to = now - add;
	    	// 	nd = safeadd(dist, cost);
		    // 	pq.push({{-safeadd(nd, geth(to)), -to}, -nd});

	    	// 	add *= 2;
	    	// 	cost = safeadd(cost, cost);
	    	// }
	    }

	    cout << ans << endl;
    }


    return 0;
}


Measured memory_bytes: 18840