#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005
ll INF = 1001001001001001001;
int main() {
    int T;
    cin >> T;
    rep(_,T){
        ll n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        ll ans = INF;
        map<ll,ll> mp;
        priority_queue<P,vector<P>,greater<P>> que;
        mp[n] = 0;
        que.push(P(0,n));
        while(que.size()>0){
            ll val = que.top().first;
            ll num = que.top().second;
            que.pop();
            if(val>ans)break;
            if(val>mp[num])continue;
            // cout << num << ' ' << val << endl;
            if(INF/num >= d){
                ans = min(ans, num*d+val);
            }
            if(num==1)break;

            ll tmp = val;
            ll nn = num;
            while(nn%2!=0){
                nn++;
                tmp += d;
            }
            tmp += a;
            nn /= 2;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }

            tmp = val;
            nn = num;
            while(nn%3!=0){
                nn++;
                tmp += d;
            }
            tmp += b;
            nn /= 3;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }

            tmp = val;
            nn = num;
            while(nn%5!=0){
                nn++;
                tmp += d;
            }
            tmp += c;
            nn /= 5;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }

            if(num < 2) continue;
            tmp = val;
            nn = num;
            while(nn%2!=0){
                nn--;
                tmp += d;
            }
            tmp += a;
            nn /= 2;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }

            if(num < 3) continue;
            tmp = val;
            nn = num;
            while(nn%3!=0){
                nn--;
                tmp += d;
            }
            tmp += b;
            nn /= 3;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }

            if(num < 5) continue;
            tmp = val;
            nn = num;
            while(nn%5!=0){
                nn--;
                tmp += d;
            }
            tmp += c;
            nn /= 5;
            if(mp.find(nn) != mp.end()){
                if(mp[nn] > tmp){
                    mp[nn] = tmp;
                    que.push(P(tmp,nn));
                }
            }else{
                mp[nn] = tmp;
                que.push(P(tmp,nn));
            }
        }
        
        cout << ans << endl;
    }
    return 0;
}




Measured memory_bytes: 4356