#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1e18;

long long int a, b, c, d;
map<long long int, long long int> memo;

long long int DFS(long long int x){
    if(memo.find(x) != memo.end()) return memo[x];

    long long int ans = INF;
    ans = min({ans, DFS(x/2) + (x%2) * d + a, DFS((x+1)/2) + (2-x%2) * d + a});
    ans = min({ans, DFS(x/3) + (x%3) * d + b, DFS((x+2)/3) + (3-x%3) * d + b});
    ans = min({ans, DFS(x/5) + (x%5) * d + c, DFS((x+4)/5) + (5-x%5) * d + c});
    if(x <= INF / d) ans = min(ans, x*d);

    return memo[x] = ans;
}

int main(){
    int t;
    cin >> t;

    for(int i=0; i<t; i++){
        long long int n;
        cin >> n >> a >> b >> c >> d;

        memo.clear();
        memo[0] = 0;
        memo[1] = d;

        cout << DFS(n) << endl;
    }
    return 0;
}