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

int main()
{
    int T;cin >> T;
    for (int i=0;i<T;i++)
    {
        ll N,A,B,C,D;
        cin >> N >> A >> B >> C >> D;
        priority_queue<ll> que;
        que.push(N);
        map<ll,ll> dp;
        dp[N]=0;
        while (!que.empty())
        {
            ll v=que.top();
            que.pop();
            if (v%2==0)
            {
                if (dp[v/2]==0)
                {
                    dp[v/2]=min(dp[v]+A,dp[v]+v/2*D);
                    que.push(v/2);
                }
                else
                {
                    if (dp[v/2]>dp[v]+min(A,v/2*D))
                    {
                        dp[v/2]=dp[v]+min(A,v/2*D);
                        que.push(v/2);
                    }
                }
            }
            else
            {
                if (dp[(v+1)/2]==0)
                {
                    dp[(v+1)/2]=min(dp[v]+D+A,dp[v]+(v-(v+1)/2)*D);
                    que.push((v+1)/2);
                }
                else
                {
                    if (dp[(v+1)/2]>min(dp[v]+D+A,dp[v]+(v-(v+1)/2)*D))
                    {
                        dp[(v+1)/2]=min(dp[v]+D+A,dp[v]+(v-(v+1)/2)*D);
                        que.push((v+1)/2);
                    }
                }
                if (v-1>=0)
                {
                if (dp[(v-1)/2]==0)
                {
                    dp[(v-1)/2]=dp[v]+D+min(A,(v-1)/2*D);
                    que.push((v-1)/2);
                }
                else
                {
                    if (dp[(v-1)/2]>dp[v]+D+min(A,(v-1)/2*D))
                    {
                        dp[(v-1)/2]=dp[v]+min(A,(v-1)/2*D)+D;
                        que.push((v-1)/2);
                    }
                }
                }
            }
            if (v%3==0)
            {
                if (dp[v/3]==0)
                {
                    dp[v/3]=min(dp[v]+B,dp[v]+2*v/3*D);
                    que.push(v/3);
                }
                else
                {
                    if (dp[v/3]>dp[v]+min(B,2*v/3*D))
                    {
                        dp[v/3]=dp[v]+min(B,2*v/3*D);
                        que.push(v/3);
                    }
                }
            }
            else
            {
                int r=v%3;
                if (dp[(v+3-r)/3]==0)
                {
                    dp[(v+3-r)/3]=dp[v]+D*(3-r)+min(B,2*(v+3-r)/3*D);
                    que.push((v+3-r)/3);
                }
                else
                {
                    if (dp[(v+3-r)/3]>dp[v]+D*(3-r)+min(B,2*(v+3-r)/3*D))
                    {
                        dp[(v+3-r)/3]=dp[v]+D*(3-r)+min(B,2*(v+3-r)/3*D);
                        que.push((v+3-r)/3);
                    }
                }
                if (v-r>=0){
                if (dp[(v-r)/3]==0)
                {
                    dp[(v-r)/3]=dp[v]+r*D+min(B,2*(v-r)/3*D);
                    que.push((v-r)/3);
                }
                else
                {
                    if (dp[(v-r)/3]>dp[v]+D*r+min(B,2*(v-r)/3*D))
                    {
                        dp[(v-r)/3]=dp[v]+D*r+min(B,2*(v-r)/3*D);
                        que.push((v-r)/3);
                    }
                }
                }
            }
            if (v%5==0)
            {
                if (dp[v/5]==0)
                {
                    dp[v/5]=min(dp[v]+C,dp[v]+4*v/5*D);
                    que.push(v/5);
                }
                else
                {
                    if (dp[v/5]>dp[v]+min(C,4*v/5*D))
                    {
                        dp[v/5]=dp[v]+min(C,4*v/5*D);
                        que.push(v/5);
                    }
                }
            }
            else
            {
                int r=v%5;
                if (dp[(v+5-r)/5]==0)
                {
                    dp[(v+5-r)/5]=dp[v]+D*(5-r)+min(C,4*(v+5-r)/5*D);
                    que.push((v+5-r)/5);
                }
                else
                {
                    if (dp[(v+5-r)/5]>dp[v]+D*(5-r)+min(C,4*(v+5-r)/5*D))
                    {
                        dp[(v+5-r)/5]=dp[v]+D*(5-r)+min(C,4*(v+5-r)/5*D);
                        que.push((v+5-r)/5);
                    }
                }
                if (v-r>=0){
                if (dp[(v-r)/5]==0)
                {
                    dp[(v-r)/5]=dp[v]+r*D+min(C,4*(v-r)/5*D);
                    que.push((v-r)/5);
                }
                else
                {
                    if (dp[(v-r)/5]>dp[v]+D*r+min(C,4*(v-r)/5*D))
                    {
                        dp[(v-r)/5]=dp[v]+D*r+min(C,4*(v-r)/5*D);
                        que.push((v-r)/5);
                    }
                }
                }
            }
        }
        cout << dp[0] << endl;
    }
    return 0;
}

Measured memory_bytes: 4412