#include <bits/stdc++.h>

using namespace std;

int64_t N;

int A, B, C;

int64_t Co[5000][5000];

int64_t Comb(int n, int k) {
    if(k == 0 || k == n) return 1;
    if(Co[n][k]) return Co[n][k];
    Co[n][k] = Comb(n-1, k) + Comb(n-1, k-1);
    if(Co[n][k] >= 1e16) Co[n][k] = 1e16;
    return Co[n][k];
}

bool good(int total) {
    int64_t nodes = 0;

    for(int a=0; a*A<=total; a++) {
        for(int b=0; a*A + b*B<=total; b++) {
            int c = (total - a*A - b*B) / C;

            int64_t r1 = Comb(a+b+c, a),
                    r2 = Comb(b+c, b);

            if(log(r1) + log(r2) > log(1e16)) return true;

            nodes += r1 * r2;

            if(nodes >= N) return true;
        }
    }
    return false;
}


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

    while(t--) {
        cin>>N>>A>>B>>C;

        if(A < C) swap(A, C);
        if(A < B) swap(A, B);
        if(B < C) swap(B, C);

        int upb = 0;

        for(int64_t pw = 1; pw <= N; pw *= 3)
            upb += A;

        int sol = -1, step;
        for(step=1; step<=upb; step<<=1);
        for(step>>=1; step; step>>=1) {
            if(step + sol <= upb && !good(step + sol))
                sol += step;
        }

        cout<<sol+1<<'\n';
    }
    return 0;
}