#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

map <LL,LL> mp;
LL n,a,b,c,d,T;

LL solve(LL x){
	if(mp.find(x) != mp.end()) return mp[x];
	LL tmp = (INF / d < x ? INF : x * d);
	for(LL i = -4;i <= 4;i ++){
		if(x + i < 0) continue;
		if(i >= -1 && i <= 1) if((x + i) % 2 == 0) tmp = min(tmp,solve((x + i) / 2) + a + (i < 0 ? -i : i) * d);
		if(i >= -2 && i <= 2) if((x + i) % 3 == 0) tmp = min(tmp,solve((x + i) / 3) + b + (i < 0 ? -i : i) * d);
		if(i >= -4 && i <= 4) if((x + i) % 5 == 0) tmp = min(tmp,solve((x + i) / 5) + c + (i < 0 ? -i : i) * d);
	}
	mp[x] = tmp; return tmp;
}

int main(){
	cin >> T;
	while(T --){
		mp.clear();
		cin >> n >> a >> b >> c >> d;
		mp[0] = 0; mp[1] = d;
		cout << solve(n) << '\n';
	}
	return 0;
}