var dic = {};
var queue = [];

function updateDic(j, n, a, b, c, d) {
	// console.log("updateDic");
	// console.log({
	// 	j: j,
	// 	n: n,
	// 	a: a,
	// 	b: b,
	// 	c: c,
	// 	d: d
	// });
	const pay = dic[j];
	// a
	var tmpJ = j * 2;
	var tmpPay = pay + a;
	if (tmpJ < n * 2) {
		if (!dic[tmpJ] || tmpPay < dic[tmpJ]) {
			dic[tmpJ] = tmpPay;
			queue.push(tmpJ);
		}
	}
	// b
	var tmpJ = j * 3;
	var tmpPay = pay + b;
	if (tmpJ < n * 3) {
			if (!dic[tmpJ] || tmpPay < dic[tmpJ]) {
			dic[tmpJ] = tmpPay;
			queue.push(tmpJ);
		}
	}
	// c
	var tmpJ = j * 5;
	var tmpPay = pay + c;
	if (tmpJ < n * 5) {
			if (!dic[tmpJ] || tmpPay < dic[tmpJ]) {
			dic[tmpJ] = tmpPay;
			queue.push(tmpJ);
		}
	}
	// d(+1)
	var tmpJ = j + 1;
	var tmpPay = pay + d;
	if (tmpJ < n * 2) {
		if (!dic[tmpJ] || tmpPay < dic[tmpJ]) {
			dic[tmpJ] = tmpPay;
			queue.push(tmpJ);
		}
	}
	// d(-1)
	var tmpJ = j - 1;
	var tmpPay = pay + d;
	if (0 < tmpJ) {
		if (!dic[tmpJ] || tmpPay < dic[tmpJ]) {
			dic[tmpJ] = tmpPay;
			queue.push(tmpJ);
		}
	}
}

function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	const inputLines = input.split("\n");
	const line0 = inputLines[0];
	const questions = parseInt(line0, 10);

	for (var i = 1; i <= questions; i++) {
		var result = Number.MAX_VALUE;
		var pays = {};
		// if (i != 5) {continue;}
		dic = {};
		const line1 = inputLines[i];
		const line1vars = line1.split(" ");
		const n = parseInt(line1vars[0], 10);
		const a = parseInt(line1vars[1], 10);
		const b = parseInt(line1vars[2], 10);
		const c = parseInt(line1vars[3], 10);
		const d = parseInt(line1vars[4], 10);

		dic[1] = d;
		queue.push(1);
		while(0 < queue.length) {
			var j = queue.shift();
			updateDic(j, n, a, b, c, d);
		}

		// console.log({
		// 	n: n,
		// 	a: a,
		// 	b: b,
		// 	c: c,
		// 	d: d,
		// 	dic: dic
		// });
		console.log(dic[n]);
	}

	// tmp = input[1].split(" ");
	// //文字列から10進数に変換するときはparseIntを使います
	// var a = parseInt(input[0], 10);
	// var b = parseInt(tmp[0], 10);
	// var c = parseInt(tmp[1], 10);
	// var s = input[2];

	//出力
	// console.log('%d %s',a+b+c,s);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

// node index.js
// 1
// 2 3
// test
// (Ctrl + D)