#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef unsigned long long LL;
typedef pair<LL, LL> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int main(){
    int T;
    cin>>T;
    REP(t,T){
        LL N,A,B,C,D;
        cin>>N>>A>>B>>C>>D;
        map<LL,LL>dp;
        dp[N]=0;
        priority_queue<LL>que;
        que.push(N);
        while(!que.empty()){
            LL nowN=que.top();que.pop();
            //cout<<nowN<<endl;
            if(nowN<=0)break;
            if(dp.find(0)==dp.end()){
                dp[0]=dp[nowN]+nowN*D;
            }else{
                dp[0]=min(dp[0],dp[nowN]+nowN*D);
            }
            LL div=nowN%2;
            if(dp.find((nowN-div)/2LL)==dp.end()){
                dp[(nowN-div)/2LL]=dp[nowN]+div*D+A;
                que.push((nowN-div)/2LL);
            }else{
                dp[(nowN-div)/2LL]=min(dp[(nowN-div)/2LL],dp[nowN]+div*D+A);
            }
            if(div!=0){
                if(dp.find((nowN+2LL-div)/2LL)==dp.end()){
                    dp[(nowN+2LL-div)/2LL]=dp[nowN]+(2LL-div)*D+A;
                    que.push((nowN+2LL-div)/2LL);
                }else{
                    dp[(nowN+2LL-div)/2LL]=min(dp[(nowN+2LL-div)/2LL],dp[nowN]+(2LL-div)*D+A);
                }
            }
            div=nowN%3;
            if(dp.find((nowN-div)/3LL)==dp.end()){
                dp[(nowN-div)/3LL]=dp[nowN]+div*D+B;
                que.push((nowN-div)/3LL);
            }else{
                dp[(nowN-div)/3LL]=min(dp[(nowN-div)/3LL],dp[nowN]+div*D+B);
            }
            if(div!=0){
                if(dp.find((nowN+3LL-div)/3LL)==dp.end()){
                    dp[(nowN+3LL-div)/3LL]=dp[nowN]+(3LL-div)*D+B;
                    que.push((nowN+3LL-div)/3LL);
                }else{
                    dp[(nowN+3LL-div)/3LL]=min(dp[(nowN+3LL-div)/3LL],dp[nowN]+(3LL-div)*D+B);
                }
            }
            div=nowN%5LL;
            if(dp.find((nowN-div)/5LL)==dp.end()){
                dp[(nowN-div)/5LL]=dp[nowN]+div*D+C;
                que.push((nowN-div)/5LL);
            }else{
                dp[(nowN-div)/5LL]=min(dp[(nowN-div)/5LL],dp[nowN]+div*D+C);
            }
            if(div!=0){
                if(dp.find((nowN+5LL-div)/5LL)==dp.end()){
                    dp[(nowN+5LL-div)/5LL]=dp[nowN]+(5LL-div)*D+C;
                    que.push((nowN+5LL-div)/5LL);
                }else{
                    dp[(nowN+5LL-div)/5LL]=min(dp[(nowN+5LL-div)/5LL],dp[nowN]+(5LL-div)*D+C);
                }
            }
        }
        cout<<dp[0]<<endl;
    }
    return 0;
}

Measured memory_bytes: 4520