import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.bigint;

void main()
{
    auto T = readln.chomp.to!int;
    foreach (_t; 0..T) {
        auto nabcd = readln.split.to!(long[]);
        BigInt N = nabcd[0];
        BigInt A = nabcd[1];
        BigInt B = nabcd[2];
        BigInt C = nabcd[3];
        BigInt D = nabcd[4];

        BigInt[BigInt] memo;
        BigInt solve(BigInt n) {
            if (n == BigInt(0)) return BigInt(0);
            if (n == BigInt(1)) return D;
            if (n !in memo) {
                auto res = n * D;
                res = min(res, solve(n / BigInt(2)) + A + (n % BigInt(2)) * D);
                res = min(res, solve(n / BigInt(3)) + B + (n % BigInt(3)) * D);
                res = min(res, solve(n / BigInt(5)) + C + (n % BigInt(5)) * D);
                memo[n] = res;
            }
            return memo[n];
        }
        writeln(solve(N));
    }
}