#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n,a,b,c,d,ans;
inline void upda(LL v){ if (v<0) return; if (ans == -1) ans = v; else ans = min(ans,v);  }
inline void upd(LL &ans,LL v){ if (v<0) return; if (ans == -1) ans = v; else ans = min(ans,v);  }
inline int Log(LL n,LL k){
	LL ret = 0,r = 1;
	while (n / r >= k) r *= k,++ret; ++ret;
	return ret;
}
inline LL solve(LL v){
	LL ans = 0;
	while (v%2==0) v/=2,ans+=a;
	while (v%3==0) v/=3,ans+=b;
	while (v%5==0) v/=5,ans+=c;
	if (v>1) return -1;
	return ans;
}
inline LL power(LL a,LL b){ static LL r; r=1; while (b){ if (b&1) r*=a; a*=a,b>>=1; } return r; }
int tmp[100];
inline LL DP(int n,int *a,int k){
	static LL v0,v1,t0,t1; static int i;
	v0 = 0,v1 = 1;
	for (int i = n; i >= 0; --i){
		t0 = t1 = -1;
		if (v0 > -1) upd(t0,v0 + a[i]),upd(t1,v0 + abs(a[i]+1));
		if (v1 > -1) upd(t0,v1 + abs(a[i]-k)),upd(t1,v1 + abs(a[i]+1-k));
		v0 = t0,v1 = t1;
	}
	if (v0 == -1) return ans;
	return v0;
}
inline LL DP1(int n,int *a,int k){
	static LL v0,v1,t0,t1; static int i;
	v0 = 0,v1 = ans;
	for (int i = n; i >= 0; --i){
		t0 = t1 = -1;
		if (v0 > -1) upd(t0,v0 + a[i]),upd(t1,v0 + abs(a[i]+1));
		if (v1 > -1) upd(t0,v1 + abs(a[i]-k)),upd(t1,v1 + abs(a[i]+1-k));
		v0 = t0,v1 = t1;
	}
	if (v0 == -1) return ans;
	return v0;
}
map<LL,LL>mp;
inline void solve1(LL n,LL now){
	upda(n*d+now); if (n <= 1) return;
	if (ans != -1 && now >= ans) return;
	if (mp.count(n) && now >= mp[n]) return; mp[n] = now;
	if (n % 2 == 0) solve1(n/2,now+a); else solve1(n/2+1,now+d+a),solve1(n/2,now+d+a);
	if (n % 3 == 0) solve1(n/3,now+b); else solve1(n/3,now+d*(n%3)+b),solve1(n/3+1,now+d*(3-n%3)+b);
	if (n % 5 == 0) solve1(n/5,now+c); else solve1(n/5,now+d*(n%5)+c),solve1(n/5+1,now+d*(5-n%5)+c);
	for (int i = -2; i <= 2; ++i){
		LL v = n + i; if (v < 0) continue;
		if (v % 2 == 0) solve1(v/2,now+a+d*abs(i));
		if (v % 3 == 0) solve1(v/3,now+b+d*abs(i));
		if (v % 5 == 0) solve1(v/5,now+c+d*abs(i));
	}
	if (n <= 1000){
		solve1(n-1,now+d);
	//	solve1(n+1,now+d);
	}
}
inline void solve(){
	int i,j;
	int l2,l3,l5;
	LL v,s,t;
	cin >> n >> a >> b >> c >> d; ans = -1; upda(n*d);
	for (i = 1; i <= 2000 && i <= n; ++i)
	for (s = i,j = -2000; j <= 2000; ++j){
		t = n + j; if (t <= 0 || t % s != 0) continue;
		v = solve(t/s); if (v == -1) continue; upda(d * (abs(j)+i) + v);
	}
	l2 = Log(n,2); upda(l2 * a + abs((1ll<<l2)-n) * d + d);
	l3 = Log(n,3); upda(l3 * b + abs(power(3,l3)-n) * d + d);
	l5 = Log(n,5); upda(l5 * c + abs(power(5,l5)-n) * d + d);
	for (v = 0,t = n,i = l2-1; i >= 0; --i) s = power(2,i),v += t / s,t %= s; if (!t) upda((l2-1) * a + d * v);
	for (v = 0,t = n,i = l3-1; i >= 0; --i) s = power(3,i),v += t / s,t %= s; if (!t) upda((l3-1) * b + d * v);
	for (v = 0,t = n,i = l5-1; i >= 0; --i) s = power(5,i),v += t / s,t %= s; if (!t) upda((l5-1) * c + d * v);
	
	for (v = 0,t = n,i = l2-1; i >= 0; --i) s = power(2,i),tmp[i] = t / s,t %= s; upda((l2-1)*a + DP1(l2-1,tmp,2) * d);
	for (v = 0,t = n,i = l3-1; i >= 0; --i) s = power(3,i),tmp[i] = t / s,t %= s; upda((l3-1)*b + DP1(l3-1,tmp,3) * d);
	for (v = 0,t = n,i = l5-1; i >= 0; --i) s = power(5,i),tmp[i] = t / s,t %= s; upda((l5-1)*c + DP1(l5-1,tmp,5) * d);
	
	for (v = 0,t = n,i = l2-1; i >= 0; --i) s = power(2,i),tmp[i] = t / s,t %= s; upda(l2*a + DP(l2-1,tmp,2) * d);
	for (v = 0,t = n,i = l3-1; i >= 0; --i) s = power(3,i),tmp[i] = t / s,t %= s; upda(l3*b + DP(l3-1,tmp,3) * d);
	for (v = 0,t = n,i = l5-1; i >= 0; --i) s = power(5,i),tmp[i] = t / s,t %= s; upda(l5*c + DP(l5-1,tmp,5) * d);
	
	mp.clear();
	solve1(n,0);
	
	cout << ans << '\n';
}

int main(){
	int T; cin >> T;
	while (T--) solve();
	return 0;
}

Measured memory_bytes: 4820