#include <bits/stdc++.h>
using namespace std;

int main() {
	long long t;
	cin >> t;
	vector<vector<long long>>tc(t, vector<long long>(5));
	for (int i = 0; i < t; i++)cin >> tc.at(i).at(0) >> tc.at(i).at(1) >> tc.at(i).at(2) >> tc.at(i).at(3) >> tc.at(i).at(4);
	for (int i = 0; i < t; i++) {
		long long ans = 0;
		map<long long,long long>dp;
		dp[tc.at(i).at(0)] = 0;
		priority_queue<long long, vector<long long>, less<long long>> q;
		set<long long>discovered;
		q.push(tc.at(i).at(0));
		while (q.size() >= 1) {
			long long k = q.top();
			if (discovered.count(k)) {
				q.pop();
				continue;
			}
			if (k == 1) {
				q.pop();
				continue;
			}
			long long am, bm, cm;
			am = k % 2;
			bm = k % 3;
			cm = k % 5;
			if (am == 0) {
				long long aexact = k / 2;
				long long aexacttmp;
				if ((k - aexact) < tc.at(i).at(1)/ tc.at(i).at(4)) aexacttmp = dp[k] + (k - aexact) * tc.at(i).at(4);
				else aexacttmp = dp[k] + tc.at(i).at(1);
				if (dp.count(aexact))dp.at(aexact) = min(dp.at(aexact), aexacttmp);
				else dp[aexact] = aexacttmp;
				q.push(aexact);
				//cout << "aexacttmp:" << aexacttmp << endl;
			}
			else {
				long long aup = (k + (2 - am)) / 2;
				long long adown = (k - am) / 2;
				long long auptmp, adowntmp;
				if ((k - aup) < (tc.at(i).at(1) + tc.at(i).at(4) * (2 - am))/ tc.at(i).at(4))auptmp = dp[k] + (k - aup) * tc.at(i).at(4);
				else auptmp = dp[k] + tc.at(i).at(1) + tc.at(i).at(4) * (2 - am);
				if (dp.count(aup))dp.at(aup) = min(dp.at(aup), auptmp);
				else dp[aup] = auptmp;
				q.push(aup);
				if ((k - adown) < (tc.at(i).at(1) + tc.at(i).at(4) * am) / tc.at(i).at(4))adowntmp = dp[k] + (k - adown) * tc.at(i).at(4);
				else adowntmp = dp[k] + tc.at(i).at(1) + tc.at(i).at(4) * am;
				if (dp.count(adown))dp.at(adown) = min(dp.at(adown), adowntmp);
				else dp[adown] = adowntmp;
				q.push(adown);
				//cout << "auptmp:" << auptmp << endl;
				//cout << "adowntmp:" << adowntmp << endl;
			}
			if (bm == 0) {
				long long bexact = k / 3;
				long long bexacttmp;
				if ((k - bexact)  < tc.at(i).at(2) / tc.at(i).at(4)) bexacttmp = dp[k] + (k - bexact) * tc.at(i).at(4);
				else bexacttmp = dp[k] + tc.at(i).at(2);
				if (dp.count(bexact))dp.at(bexact) = min(dp.at(bexact), bexacttmp);
				else dp[bexact] = bexacttmp;
				q.push(bexact);
				//cout << "bexacttmp:" << bexacttmp << endl;
			}
			else {
				long long bup = (k + (3 - bm)) / 3;
				long long bdown = (k - bm) / 3;
				long long buptmp, bdowntmp;
				if ((k - bup) < (tc.at(i).at(2) + tc.at(i).at(4) * (3 - bm)) / tc.at(i).at(4))buptmp = dp[k] + (k - bup) * tc.at(i).at(4);
				else buptmp = dp[k] + tc.at(i).at(2) + tc.at(i).at(4) * (3 - bm);
				if (dp.count(bup))dp.at(bup) = min(dp.at(bup), buptmp);
				else dp[bup] = buptmp;
				q.push(bup);
				if ((k - bdown)  < (tc.at(i).at(2) + tc.at(i).at(4) * bm) / tc.at(i).at(4))bdowntmp = dp[k] + (k - bdown) * tc.at(i).at(4);
				else bdowntmp = dp[k] + tc.at(i).at(2) + tc.at(i).at(4) * bm;
				if (dp.count(bdown))dp.at(bdown) = min(dp.at(bdown), bdowntmp);
				else dp[bdown] = bdowntmp;
				q.push(bdown);
				//cout << "buptmp:" << buptmp << endl;
				//cout << "bdowntmp:" << bdowntmp << endl;
			}
			if (cm == 0) {
				long long cexact = k / 5;
				long long cexacttmp;
				if ((k - cexact) < tc.at(i).at(3)/ tc.at(i).at(4)) cexacttmp = dp[k] + (k - cexact) * tc.at(i).at(4);
				else cexacttmp = dp[k] + tc.at(i).at(3);
				if (dp.count(cexact))dp.at(cexact) = min(dp.at(cexact), cexacttmp);
				else dp[cexact] = cexacttmp;
				q.push(cexact);
				//cout << "cexacttmp:" << cexacttmp << endl;
			}
			else {
				long long cup = (k + (5 - cm)) / 5;
				long long cdown = (k - cm) / 5;
				long long cuptmp, cdowntmp;
				if ((k - cup) < (tc.at(i).at(3) + tc.at(i).at(4) * (5 - cm)) / tc.at(i).at(4))cuptmp = dp[k] + (k - cup) * tc.at(i).at(4);
				else cuptmp = dp[k] + tc.at(i).at(3) + tc.at(i).at(4) * (5 - cm);
				if (dp.count(cup))dp.at(cup) = min(dp.at(cup), cuptmp);
				else dp[cup] = cuptmp;
				q.push(cup);
				if ((k - cdown) < (tc.at(i).at(3) + tc.at(i).at(4) * cm) / tc.at(i).at(4))cdowntmp = dp[k] + (k - cdown) * tc.at(i).at(4);
				else cdowntmp = dp[k] + tc.at(i).at(3) + tc.at(i).at(4) * cm;
				if (dp.count(cdown))dp.at(cdown) = min(dp.at(cdown), cdowntmp);
				else dp[cdown] = cdowntmp;
				q.push(cdown);
				//cout << "cuptmp:" << cuptmp << endl;
				//cout << "cdowntmp:" << cdowntmp << endl;
			}
			discovered.insert(k);
			q.pop();
		}
		cout << dp.at(1)+tc.at(i).at(4) << endl;
	}
}

Measured memory_bytes: 5168