fn dfs(
    n: usize,
    a: usize,
    b: usize,
    c: usize,
    d: usize,
    x: usize,
    memo: &mut HashMap<usize, usize>,
) -> usize {
    let mut res = std::usize::MAX;
    if n == 0 {
        return min(res, x);
    } else if n == 1 {
        return min(res, x + d);
    }

    for &p in [(2, a), (3, b), (5, c)].iter().rev() {
        if n >= p.0 {
            let flor = n / p.0;
            res = min(
                dfs(flor, a, b, c, d, x + p.1 + (n - flor * p.0) * d, memo),
                res,
            );
            if n % p.0 != 0 {
                let ceil = n / p.0 + 1;
                res = min(
                    dfs(ceil, a, b, c, d, x + p.1 + (ceil * p.0 - n) * d, memo),
                    res,
                );
            }
        }
    }
    match memo.get_mut(&n) {
        Some(v) => {
            *v = min(res, *v);
        }
        None => {
            memo.insert(n, res);
        }
    };
    res
}

fn solve() {
    let t: usize = read();
    'outer: for i in 0..t {
        let n: usize = read();
        let (a, b): (usize, usize) = (read::<usize>(), read::<usize>());
        let (c, d): (usize, usize) = (read::<usize>(), read::<usize>());
        let mut memo: HashMap<usize, usize> = HashMap::new();
        let mut que = BinaryHeap::new();
        que.push((Reverse(0), Reverse(n)));

        while let Some((Reverse(cost), Reverse(n))) = que.pop() {
            if n == 0 {
                memo.insert(0, cost);
                break;
            } else if n == 1 {
                memo.insert(0, cost + d);
                break;
            }
            match memo.get_mut(&n) {
                Some(v) => {
                    if *v <= cost {
                        continue;
                    } else {
                        *v = cost;
                    }
                }
                None => {
                    memo.insert(n, cost);
                }
            };

            que.push((Reverse(cost.wrapping_add(n.wrapping_mul(d))), Reverse(0)));
            for &p in [(2, a), (3, b), (5, c)].iter().rev() {
                if n >= p.0 {
                    let flor = n / p.0;
                    que.push((Reverse(cost + p.1 + (n - flor * p.0) * d), Reverse(flor)));
                    if n % p.0 != 0 {
                        let ceil = n / p.0 + 1;
                        que.push((Reverse(cost + p.1 + (ceil * p.0 - n) * d), Reverse(ceil)));
                    }
                }
            }
        }
        println!("{}", memo.get(&0).expect("error"));
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 2552