#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
const long long INF=1e18;
map<long long,long long>F;
long long A,B,C,D;
long long calc(long long n)
{
	if(F.count(n))return F[n];
	long long ans=INF;
	if(n<=INF/D)ans=n*D;
	for(int i=-1;i<=1;i++)
		if(n+i>0&&(n+i)%2==0&&(n+i)/2<n)
			ans=min(ans,calc((n+i)/2)+abs(i)*D+A);
	for(int i=-2;i<=2;i++)
		if(n+i>0&&(n+i)%3==0&&(n+i)/3<n)
			ans=min(ans,calc((n+i)/3)+abs(i)*D+B);
	for(int i=-4;i<=4;i++)
		if(n+i>0&&(n+i)%5==0&&(n+i)/5<n)
			ans=min(ans,calc((n+i)/5)+abs(i)*D+C);
	return F[n]=ans;
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		long long n;
		cin>>n>>A>>B>>C>>D;
		F.clear();
		cout<<calc(n)<<"\n";
	}
	return 0;
}