#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int NMAX = 45;
ll DP[NMAX + 5];

#define FU(i, a, b) for (int i = a; i < b; i++)
#define fu(i, b) FU(i, 0, b)

const ll inf = 1000000000000000000ll;

void solve() {
	ll N, A, B, C;
	scanf("%lld %lld %lld %lld", &N, &A, &B, &C);
	if (B < A) swap(A, B);
	if (C < A) swap(A, C);
	if (C < B) swap(B, C);

	DP[0] = DP[1] = 0;
	FU(i, 2, NMAX + 1) {
		DP[i] = inf;
		ll best = inf;
		fu(p, i) fu(q, i) {
			int la = i - p - q;
			if (la < 0) continue;
			best = min(best, max((p > 0) ? A + DP[p] : 0, max((q > 0) ? B + DP[q] : 0, (la > 0) ? C + DP[la] : 0)));
		}
		DP[i] = best;
	}
	vector<ll> p, V;
	int lim = NMAX;
	while (DP[lim] == DP[lim-1]) lim--;
	p.push_back(lim); V.push_back(DP[lim]);

	auto f = [&](ll x) {
		if (x < lim) return DP[x];
		int pos = upper_bound(p.begin(), p.end(), x) - p.begin();
		pos--;
		if (pos < V.size()) return V[pos];
		return V.back() + A;
	};

	auto f2 = [&](ll v) -> ll {
        if (V[0] > v) {
            int pos = upper_bound(DP, DP + NMAX + 1, v) - DP;
            while (pos < NMAX && DP[pos] <= v) pos++;
            while (pos > 0 && DP[pos] > v) pos--;
            return pos;
        }
        int pos = upper_bound(V.begin(), V.end(), v) - V.begin();
        pos--;
        return p[pos+1]-1;
	};

	while (p.back() <= N) {
		ll x = f2(V.back() - A);
		ll y = f2(V.back() - B);
		ll z = f2(V.back() - C);
		ll newval = A + f(x + 1);
		newval = min(newval, B + f(y+1));
		newval = min(newval, C + f(z+1));
		p.push_back(x + y + z + 1);
		V.push_back(newval);
	}
	printf("%lld\n", f(N));
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}