#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF3 1000000000000

using namespace std;

ll a,b,c,d;
map<ll,ll> s;

ll dfs(ll n){
	if(n==0){
		return 0;
	}
	if(s.count(n)){
		return s[n];
	}
	ll &ans=s[n];
	ans=((ll)1e15)/n<d?1e15:n*d;
	ans=min(ans,dfs(n/2)+a+(n%2)*d);
	ans=min(ans,dfs(n/3)+b+(n%3)*d);
	ans=min(ans,dfs(n/5)+c+(n%5)*d);
	ans=min(ans,dfs(n/2+1)+a+(2-n%2)*d);
	ans=min(ans,dfs(n/3+1)+b+(3-n%3)*d);
	ans=min(ans,dfs(n/5+1)+c+(5-n%5)*d);
	return ans;
}

ll solve0(ll n)
{
    s.clear();
    return dfs(n);
}

//
// 方針：逆から考える。
//       nに対して「±1を何回か行ってから2 or 3 or 5で割る」を繰り返して0または1にする
//
ll dp[65][65][65][2];    // dp[i][j][k][m]: 2/3/5で割ることをi/j/k回行った場合（ただしm=0は切り捨て操作、m=1はそれ+1）の最小コスト
ll val[65][65][65][2];   // val[i][j][k][m]: 上記の操作後の値

ll solve(ll n)
{
    int i, j, k, m;
    for (i = 0; i < 65; i++) {
        for (j = 0; j < 65; j++) {
            for (k = 0; k < 65; k++) {
                dp[i][j][k][0] = LINF3;
                dp[i][j][k][1] = LINF3;
            }
        }
    }

    ll ans = LINF3;
    dp[0][0][0][0] = 0;
    val[0][0][0][0] = n;
    for (i = 0; i <= 61; i++) {
        for (j = 0; j <= 61; j++) {
            for (k = 0; k <= 61; k++) {
                for (m = 0; m < 2; m++) {
                    if (dp[i][j][k][m] < LINF3) {
                        ll currval=val[i][j][k][m];
                        if ((double)dp[i][j][k][m] + (double)currval * d < LINF3) {
                            ans = MIN(ans, dp[i][j][k][m] + currval * d);   // ここから一気に0に持っていく方法で答を更新
                        }
                        if (currval <= 1) {
                            continue;     // これ以上の割り算は不要なので
                        }

                        int prime[3] = { 2, 3, 5 };
                        ll  cost[3] = { a, b, c };
                        int p;
                        for(p=0; p<3; p++) {
                            int i2 = i + (p == 0 ? 1 : 0);
                            int j2 = j + (p == 1 ? 1 : 0);
                            int k2 = k + (p == 2 ? 1 : 0);
                            ll nextval0 = currval / prime[p];
                            if((double)dp[i][j][k][m] + (double)(currval % prime[p])*d + cost[p] < LINF3){
                                dp[i2][j2][k2][0]=MIN(dp[i2][j2][k2][0], dp[i][j][k][m] + (currval % prime[p])*d + cost[p]);
                                val[i2][j2][k2][0] = nextval0;
                            }
                            if (currval % prime[p]) {
                                if ((double)dp[i][j][k][m] + (double)(prime[p] - currval % prime[p])*d + cost[p] < LINF3) {
                                    dp[i2][j2][k2][1] = MIN(dp[i2][j2][k2][1], dp[i][j][k][m] + (prime[p] - currval % prime[p])*d + cost[p]);
                                    val[i2][j2][k2][1] = nextval0 + 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }    

    return ans;
}


int main(int argc, char* argv[])
{
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        ll n;
        scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
        ll ans = solve0( n );
        //ll ans = solve( n );
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 4432