#include<bits/stdc++.h>
using namespace std;
const int M=998244353;
const int N=200005,E=524288;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
long long n,a,b,c,d;
map<long long,long long>dp;
int t;
long long dfs(long long n)
{
	if(n==0)
 		return 0;
 	if(n==1)
 		return d;
 	if(dp[n])
 		return dp[n];
 	long long y=n/5*5;
 	long long ans=1000000000000000000ll;
 	ans=min(ans,dfs(y/5)+c+(n-y)*d);
 	if(n%5!=0)
 		ans=min(ans,dfs(y/5+1)+c+(y+5-n)*d);
 	y=n/2*2;
 	ans=min(ans,dfs(y/2)+a+(n-y)*d);
 	if(n%2!=0)
 		ans=min(ans,dfs(y/2+1)+a+(y+2-n)*d);
 	y=n/3*3;
 	ans=min(ans,dfs(y/3)+b+(n-y)*d);
 	if(n%3!=0)
 		ans=min(ans,dfs(y/3+1)+b+(y+3-n)*d);
 	if((ull)n*d%M==n%M*d%M&&((ull)n*d)<=1000000000000000000ll)
 		ans=min(ans,n*d);
 	return dp[n]=ans;
} 	
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		cin>>n>>a>>b>>c>>d;
		dp.clear();
		cout<<dfs(n)<<endl;
	}
}