#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
ull n,a,b,c,d;
ull tac;
map<ull, ull> mp;
ull dfs(ull x)
{
	if (x<2) return x*d;
	if (mp.count(x)) return mp[x];
	ull r=x*d;
	//cout <<r<<" ############\n";
	r=min(r,(x%2)*d+dfs(x/2)+a); 
	r=min(r,(x%3)*d+dfs(x/3)+b); 
	r=min(r,(x%5)*d+dfs(x/5)+c);
	r=min(r,(2-(x%2))*d+dfs((x+1)/2)+a); 
	r=min(r,(3-(x%3))*d+dfs((x+2)/3)+b); 
	r=min(r,(5-(x%5))*d+dfs((x+4)/5)+c); 
	return mp[x]=r;
}
void Main()
{
	mp.clear();
	cin >>n>>a>>b>>c>>d;
	cout <<dfs(n)<<"\n";
} 
int main()
{
	cin >>tac;
	while (tac--) Main();
	return 0;
}