You start with the number 0 and you want to reach the number N.

You can change the number, paying a certain amount of coins, with the following operations:

* Multiply the number by 2, paying A coins.
* Multiply the number by 3, paying B coins.
* Multiply the number by 5, paying C coins.
* Increase or decrease the number by 1, paying D coins.



You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach N?

You have to solve T testcases.

Constraints

* 1 \le T \le 10
* 1 \le N \le 10^{18}
* 1 \le A, B, C, D \le 10^9
* All numbers N, A, B, C, D are integers.

Input

The input is given from Standard Input. The first line of the input is


T


Then, T lines follow describing the T testcases. Each of the T lines has the format


N A B C D


Output

For each testcase, print the answer on Standard Output followed by a newline.

Example

Input

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321


Output

20
19
26
3821859835
23441258666
import java.math.BigInteger;
import java.util.*;
import java.io.*;
import java.text.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 32768);
    static PrintWriter out = new PrintWriter(System.out);
    static StringTokenizer t;

    static String sn() {
        while (t == null || !t.hasMoreTokens()) {
            try {
                t = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return t.nextToken();
    }

    static int ni() {
        return Integer.parseInt(sn());
    }

    static long nlo() {
        return Long.parseLong(sn());
    }

    static long mod = (long) 998244353;

    static long pro(long a, long b) {
        return (a % mod * b % mod) % mod;
    }

    static long add(long a, long b) {
        return (a + b) % mod;
    }

    static long sub(long a, long b) {
        return ((a % mod - b % mod) + mod) % mod;
    }

    static long maxn = Long.MAX_VALUE;

    static int pow(int n) {
        return (int) (Math.log10(n) / Math.log10(2));
    }

    static long modpow(long x, long y) {
        long res = 1l;
//        x %= mod;
        while (y > 0) {
            if (y % 2 != 0)
                res *= x;
            x = x * x;
            y /= 2;
        }
        return res;
    }

    static class pair {
        String a;
        int b;

        pair(String x, int y) {
            a = x;
            b = y;
        }
    }

    static long modInverse(long n) {
        BigInteger n1 = new BigInteger(Long.toString(n));
        String s = (n1.modInverse(new BigInteger(Long.toString(mod)))).toString();
        return Long.parseLong(s) % mod;
    }

    static boolean v[] = new boolean[1000005];

    static void seive() {
        v[1] = true;
        for (int i = 2; i < 1000005; i++) {
            if (!v[i]) {
                for (int j = 2 * i; j < 1000005; j += i)
                    v[j] = true;
            }
        }
    }

    static boolean isprime(long n) {
        if (n == 1)
            return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static DecimalFormat df = new DecimalFormat("0.000000000000000000000");

    static class trie {
        trie a[] = new trie[26];
        int cnt = 0;
    }

    static long n, a, b, c, d;
    static long inf = (long) 4e18;
    static HashMap<Long, Long> map = new HashMap<>();

    static long f(long s, long val[], int mul[]) {
        if (s == 0)
            return 0;
        if (s == 1)
            return d;
        if (map.containsKey(s))
            return map.get(s);
        long res = inf;
        if (d < inf / s)
            res = Math.min(res, s * d);
        for (int i = 0; i < 3; i++) {
            if (s % mul[i] == 0)
                res = Math.min(res, val[mul[i]] + f(s / mul[i], val, mul));
            else {
                long down = s / mul[i] * mul[i];
                res = Math.min(res, val[mul[i]] + d * (s - down) + f(s / mul[i], val, mul));
                long up = down + mul[i];
                res = Math.min(res, val[mul[i]] + d * (up - s) + f(s / mul[i] + 1, val, mul));
            }
        }
        map.put(s, res);
        return res;
    }

    static void solve() {
        n = nlo();
        a = nlo();
        b = nlo();
        c = nlo();
        d = nlo();
        long arr[] = {-1, -1, a, b, -1, c};
        int mul[] = {2, 3, 5};
        out.println(f(n, arr, mul));
    }


    public static void main(String args[]) {
        int t = ni();
        while (t-- > 0) {
            solve();
            map.clear();
        }
        out.close();
    }
}

