//#pragma comment(linker,"/STACK:16777216") /*16Mb*/
//#pragma comment(linker,"/STACK:33554432") /*32Mb*/
#include <iostream>
#include <cstdio>
//#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <list>
#include <iomanip>
#include <set>
#include <map>
#include <sstream>
#include <string.h>
#include<fstream>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;

#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define RFOR(i,a,b) for(int (i)=(a)-1;(i)>=(b);--(i))
#define For(i,a,b) for(int (i)=(a);i<(b);++(i))
#define FoR(i,a,b) for(int (i)=(a)-1;(i)>=(b);--(i))
#define MP make_pair
#define I insert
#define mod 1000000007
#define INF 1000000001
#define PB push_back
#define x0 sdfhrthrth
#define x1 fdhttrlhn
#define y0 kihrbdb
#define y1 ugvrrtgtrg
#define eps 1e-5
#define X first
#define Y second

LL n, T;
int A, B, C;
pair<LL, int> ANS[1000000];
int h;

LL bp2(LL val, LL l, LL r)
{
    if (l==r) return l;
    LL x = (l+r)/2;
    if (ANS[x].X >= val) return bp2(val, l, x);
    return bp2(val, x+1, r);
}

int TANS(LL index)
{
    int ans = 1000000000;
    FOR (i, 0, h)
    {
        if (i && 2*ANS[i].X + ANS[i-1].X >=index) break;
        if (i != h-1 && ANS[i+1].Y + C < ANS[h-1].Y) continue;
        if (i != h-1 && ANS[i].Y + C > ans) continue;
        int pos = 0;
        FOR (j, i, h)
        {
            if (ANS[j].Y + B >= ans) break;
            if (j != h-1 && ANS[j+1].Y + B < ANS[h-1].Y) continue;
            if (j && ANS[j-1].X + ANS[i].X + ANS[j].X >= index) break;
            if (ANS[h-1].X + ANS[i].X + ANS[j].X < index) continue;
            pos = max(pos,j);
            int k = bp2(index - (ANS[i].X + ANS[j].X), j, h-1);
            pos = k;
            int QWE = 0;
            if (i) QWE = max(QWE, ANS[i].Y + C);
            if (j) QWE = max(QWE, ANS[j].Y + B);
            ans = min(ans, max(QWE, ANS[k].Y+A));
            if (ANS[j].Y + B >= ANS[k].Y + A) break;
        }
    }
    return ans;
}

LL bp(LL val, LL l, LL r)
{
    if (l==r) return l;
    LL x = (l+r+1)/2;
    if (TANS(x) == val) return bp(val, x,r);
    return bp(val, l,x-1);
}

pair<LL, int> bpt()
{
    LL ans, k1=0, k2=0, k3=0;
    LL p1=0, p2=0, p3=0;
    FOR (i,1,h)
    {
        if (ANS[i].Y + A <= ANS[h-1].Y) p1 = k1 = i;
        if (ANS[i].Y + B <= ANS[h-1].Y) p2 = k2 = i;
        if (ANS[i].Y + C <= ANS[h-1].Y) p3 = k3 = i;
    }
    ans = ANS[p1+1].Y + A;
    k1++;
    if (p2+1 < h)
    {
        if (ans == ANS[p2+1].Y + B)
            k2++;
        if (ans > ANS[p2+1].Y + B)
        {
            ans = ANS[p2+1].Y + B;
            k1 = p1;
            k2 = p2+1;
        }
    }
    if (p3+1 < h)
    {
        if (ans == ANS[p3+1].Y + C)
            k3++;
        if (ans > ANS[p3+1].Y + C)
        {
            ans = ANS[p3+1].Y + C;
            k1 = p1;
            k2 = p2;
            k3 = p3+1;
        }
    }
    return MP(ANS[k1].X+ANS[k2].X+ANS[k3].X, ans);
}
//100000000000 11 1 11
int solve()
{
    ANS[h++] = MP(0, 0);
    ANS[h++] = MP(1, 0);
    //ANS[h++] = MP(2, B);
    while (true)
    {
        pair<LL,int> Q = bpt();
        //cout<<Q.X<<" "<<Q.Y<<endl;
        ANS[h++] = Q;
        if (ANS[h-1].X >= n)
        {
            //cout << h << "\n";
            return ANS[h-1].Y;
        }
    }
}


int main()
{
    cin >> T;
    FOR (i,0,T)
    {
        h = 0;
        cin >> n >> A >> B >> C;
        if (A > B) swap(A,B);
        if (A > C) swap(A,C);
        if (B > C) swap(B,C);
        if (n==1) cout<<"0\n";
        else
        if (n==2) cout<<B<<"\n";
        else cout << solve() << "\n";
    }
    return 0;
}