open Num;;

Scanf.scanf "%d" (fun t ->
    let module M = Map.Make (struct type t = int let compare = compare end) in
    for i = 1 to t do
        Scanf.scanf " %d %d %d %d %d" (fun n a b c d ->
            let rec calc =
                let map = ref (M.add 0 (Int 0) (M.singleton 1 (Int d))) in
                fun k ->
                if M.mem k !map then M.find k !map else (
                    let ans = Int k */ Int d in
                    let ans = List.fold_left (fun acc i ->
                        if (k + i) mod 2 <> 0 then acc else
                            min_num acc (calc ((k + i) / 2) +/ Int a +/ Int d */ Int (abs i))
                            ) ans [ -1; 0; 1 ]
                    in
                    let ans = List.fold_left (fun acc i ->
                        if (k + i) mod 3 <> 0 then acc else
                            min_num acc (calc ((k + i) / 3) +/ Int b +/ Int d */ Int (abs i))
                            ) ans [ -1; 0; 1 ]
                    in
                    let ans = List.fold_left (fun acc i ->
                        if (k + i) mod 5 <> 0 then acc else
                            min_num acc (calc ((k + i) / 5) +/ Int c +/ Int d */ Int ( abs i))
                            ) ans [ -2; -1; 0; 1; 2 ]
                    in
                    map := M.add k ans !map;
                    ans
                  )
            in
            Printf.printf "%s\n" @@ string_of_num (calc n)
        )
    done
)