#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
map<ll,ll> mp;int a,b,c,d,t;ll n;
ll dfs(ll u)
{
	if(!u)return mp[0]=0;
	if(u==1)return mp[1]=d;
	if(mp.count(u))return mp[u];
	ll res=min(1e18,(double)u*d);
	ll l2=u/2,r2=(u+1)/2,l3=u/3,r3=(u+2)/3,l5=u/5,r5=(u+4)/5;
	res=min(res,dfs(l2)+a+1ll*abs(l2*2-u)*d);res=min(res,dfs(r2)+a+1ll*abs(r2*2-u)*d);
	res=min(res,dfs(l3)+b+1ll*abs(l3*3-u)*d);res=min(res,dfs(r3)+b+1ll*abs(r3*3-u)*d);
	res=min(res,dfs(l5)+c+1ll*abs(l5*5-u)*d);res=min(res,dfs(r5)+c+1ll*abs(r5*5-u)*d);
	return mp[u]=res;
}
int main()
{
	scanf("%d",&t);while(t--){scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);mp.clear();printf("%lld\n",dfs(n));}
	return 0;
}