#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,a,b,c,d;
map<int,int> cc;
int chg(int x){
	if(x==0) return 0;
	if(x==1) return d;
	if(cc[x]) return cc[x];
	int res = 1e18;
	if(x<res/d) res = x*d;
	res = min(res,chg(x/2) + (x%2)*d + a);
	if(x>2&&x%2)res = min(res,chg(x/2+1) + (2 - x%2) * d + a);
	if(x%3<2)res = min(res,chg(x/3) + (x%3)*d + b);
	if(x%3>1&&x>1)res = min(res,chg(x/3+1) + (3 - x%3) * d + b);
	if(x%5<3)res = min(res,chg(x/5) + (x%5)*d + c);
	if(x%5>2&&x>1)res = min(res,chg(x/5+1) + (5 - x%5) * d + c);
	cc[x] = res;
	return res;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		cc.clear();
		scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
		printf("%lld\n",chg(n));
	}
	return 0;
}