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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2
#define INF2 9000000000000000000

#define	MOD 1000000007

#define	Rep0(i, n)	for (auto i=0; i<n; i++)
#define	Rep1(i, n)	for (auto i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	int t;
	cin >>t;
	Rep0(tt, t) {
		ll N, A, B, C, D;
		cin >>N >>A >>B >>C >>D;
		// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;
		priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> Q1;
		priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> Q2;
		map<ll, ll> M;
		Q1.push({N, 0});
		M[N]=0;
		ll S=0;
		ll NNN=N;
		ll CCC;
		while (0!=NNN) {
			if (0==NNN%2) {
				NNN/=2;
				S+=A;
			} else {
				NNN--;
				S+=D;
			}
		}
		for(;;) {
			while(!Q1.empty()) {
				ll NN=Q1.top().at(0);
				ll CC=Q1.top().at(1);
				while ((!Q1.empty())&&(NN==Q1.top().at(0)))
					Q1.pop();
				if (0==NN) 
					S=min(S, CC);
				if (CC>=S)
					continue;
				if (0==NN%2) {
					if (S>CC+A) {
						NNN=NN/2;
						if (N!=NNN) {
							CCC=CC+A;
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
						}
					}
				} else if (S>CC+A+D) {
					NNN=NN/2;
					CCC=CC+A+D;
					if (N!=NNN) {
						if ((0==M[NNN])||(CCC<M[NNN])) {
							Q2.push({NNN, CCC});
							M[NNN]=CCC;
						}
					}
					NNN++;
					if (N!=NNN) {
						if ((0==M[NNN])||(CCC<M[NNN])) {
							Q2.push({NNN, CCC});
							M[NNN]=CCC;
						}
					}
				}
				if (0==NN%3) {
					if (S>CC+B) {
						NNN=NN/3;
						if (N!=NNN) {
							CCC=CC+B;
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
						}
					}
				} else if (1==NN%3) {
					NNN=NN/3;
					if (N!=NNN) { //-1, /3
						CCC=CC+B+D;
						if (S>CCC) 
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) { //+2, /3
						CCC=CC+B+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				} else { // 2==NN%3
					NNN=NN/3;
					if (N!=NNN) { //-2, /3
						CCC=CC+B+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) { //+1, /3
						CCC=CC+B+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				}
				if (0==NN%5) {
					if (S>CC+D) {
						NNN=NN/5;
						if (N!=NNN) {
							CCC=CC+C;
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
						}
					}
				} else if (1==NN%5) {
					NNN=NN/5;
					if (N!=NNN) {
						CCC=CC+C+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) {
						CCC=CC+C+D+D+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				} else if (2==NN%5) {
					NNN=NN/5;
					if (N!=NNN) {
						CCC=CC+C+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) {
						CCC=CC+C+D+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				} else if (3==NN%5) {
					NNN=NN/5;
					if (N!=NNN) {
						CCC=CC+C+D+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) {
						CCC=CC+C+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				} else { //4 ==NN%5
					NNN=NN/5;
					if (N!=NNN) {
						CCC=CC+C+D+D+D+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
					NNN++;
					if (N!=NNN) {
						CCC=CC+C+D;
						if (S>CCC)
							if ((0==M[NNN])||(CCC<M[NNN])) {
								Q2.push({NNN, CCC});
								M[NNN]=CCC;
							}
					}
				}
				double AA=(double)D*(double)NN+(double)CC;
				if (AA<=(double)9000000000000000000) {
					ll AAA=D*NN+CC;
					S=min(S, AAA);
				}
				/*
				if (S>CC+D) {
					NNN=NN-1;
					if (0==NNN) {
						S=min(S, CC+D);
					} else if (N!=NNN) {
						CCC=CC+D;
						if ((0==M[NNN])||(CCC<M[NNN])) {
							Q2.push({NNN, CCC});
							M[NNN]=CCC;
						}
					}
					NNN=NN+1;
					if (N!=NNN) {
						CCC=CC+D;
						if ((0==M[NNN])||(CCC<M[NNN])) {
							Q2.push({NNN, CCC});
							M[NNN]=CCC;
						}
					}
				}
				*/
			}
			swap(Q1, Q2);
			if (Q1.empty())
				break;
		}
		cout <<S <<endl;
	}
	return 0;
}



Measured memory_bytes: 4388