module deque_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    type deque
        integer(int64),pointer:: v(:)
        integer(int64):: l,r
        integer(int64):: lmax, rmax
    contains
        procedure:: init => dq_init
        procedure:: append => dq_append
        procedure:: appendleft => dq_appendleft
        procedure:: pop => dq_pop
        procedure:: popleft => dq_popleft
        procedure:: right => dq_right
        procedure:: left => dq_left
        procedure:: remaining_elements => dq_remaining_elements
        procedure:: remain => dq_remain
    end type
contains
    subroutine dq_init(dq)
        ! 初期化
        class(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end subroutine


    subroutine dq_append(dq,num)
        ! 右端に挿入
        class(deque):: dq
        integer(int64):: num
        if (dq%r+1 > dq%rmax) call dq_add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine dq_appendleft(dq,num)
        ! 左端に挿入
        class(deque):: dq
        integer(int64):: num
        if (dq%l-1 < dq%lmax) call dq_add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine dq_add_(dq)
        ! arrayの延長
        class(deque):: dq
        integer(int64):: l
        integer(int64),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(2*dq%lmax:2*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 2*dq%lmax
        dq%rmax = 2*dq%rmax
    end subroutine


    function dq_pop(dq) result(ret)
        ! 右端から取り出し
        class(deque):: dq
        integer(int64):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function dq_popleft(dq) result(ret)
        ! 左端から取り出し
        class(deque):: dq
        integer(int64):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function dq_right(dq) result(ret)
        ! 右端を確認
        class(deque):: dq
        integer(int64):: ret
        ret = dq%v(dq%r)
    end function

    function dq_left(dq) result(ret)
        ! 左端を確認
        class(deque):: dq
        integer(int64):: ret
        ret = dq%v(dq%l)
    end function

    function dq_remaining_elements(dq) result(ret)
        ! 残りの要素数
        class(deque):: dq
        integer(int64):: ret 
        ret = dq%r - dq%l + 1
    end function

    function dq_remain(dq) result(ret)
        ! 要素が残っているかどうか
        class(deque):: dq
        logical:: ret
        ret = dq%remaining_elements() > 0
    end function
end module

program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int64):: t,i
    integer(int64),allocatable:: ans(:),a(:),b(:),c(:),d(:),n(:)

    read*, t
    allocate(ans(t),a(t),b(t),c(t),d(t),n(t))
    do i=1,t
        read*, n(i),a(i),b(i),c(i),d(i)
    end do
    do i=1,t
        print*, i
        ans(i) = solve(n(i),a(i),b(i),c(i),d(i))
    end do
    
    do i=1,t
        print*, i, ans(i)
    end do

contains
    function solve(n,a,b,c,d) result(ret)
        use deque_mod
        integer(int64):: n,a,b,c,d,i
        integer(int64):: nc, nn, ret, df, v
        real(real64):: la,lb,lc,ld
        type(deque):: coin, num
        la = log10(dble(a))
        lb = log10(dble(b))
        lc = log10(dble(c))
        ld = log10(dble(d))
        call coin%init()
        call num%init()
        call coin%append(d)
        call num%append(1_8)
        ret = 9*10_8**18
        i=0
        do while(coin%remain())
            nc = coin%popleft()
            nn = num%popleft()
            df = abs(nn-n)

            if (df==0) then
                ret = min(ret,nc)
            else if (log10(dble(df))+ld <= 18d0) then
                ret  = min(ret, df*d+nc)
            end if

            if (nn<n) then 
                if (la < log10(dble(nn))+ld) then
                    v = a
                else
                    v = nn*d
                end if

                call coin%append(nc+v)
                call num%append(2*nn)
            end if

            if (nn<n) then
                if (lb < log10(dble(2*nn))+ld) then
                    v = b
                else
                    v = 2*nn*d
                end if
                call coin%append(nc+v)
                call num%append(3*nn)
            end if

            if (nn<n) then
                if (lc < log10(dble(4*nn))+ld) then
                    v = c
                else
                    v = 4*nn*d
                end if
                call coin%append(nc+v)
                call num%append(5*nn)
            end if

            if (nn < n) then
                call coin%append(nc+d)
                call num%append(nn+1)
            end if
            if (nn-1 /= 0 .and. ret > nc+d .and. nn < n) then
                call coin%append(nc+d)
                call num%append(nn-1)
            end if

            i=i+1
            if (i > 10**6) exit
        end do
    end function
end program main