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

module bst_node_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    type bst_node
        integer(int64):: key
        integer(int64):: val
        type(bst_node),pointer:: p=>null()
        type(bst_node),pointer:: c_left=>null()
        type(bst_node),pointer:: c_right=>null()
    end type
contains
    function has_key(root, key) result(ret)
        type(bst_node),pointer:: root, node
        integer(int64):: key
        logical:: ret

        ret = .false.
        node => root

        do while(associated(node))
            if (key < node%key) then
                node => node%c_left
            else if (key > node%key) then
                node => node%c_right
            else
                ret = .true.
                return
            end if
        end do
    end function


    function get_val(root, key) result(ret)
        type(bst_node),pointer:: root, node
        integer(int64):: key, ret
        node => root
        if (.not. has_key(root, key)) then
            print*, 'unexpected_access at getval!'
            stop
        end if

        do while(associated(node))
            if (key < node%key) then
                node => node%c_left
            else if (key > node%key) then
                node => node%c_right
            else
                ret = node%val
                return
            end if
        end do
    end function

    function malloc_node(key,val) result(add)
        integer(int64):: key,val
        type(bst_node),pointer:: add

        allocate(add)
        add%key=key
        add%val=val
        add%c_left => null()
        add%c_right=> null()
    end function

    subroutine add_node(root,key,val)
        type(bst_node),pointer:: root, node
        integer(int64):: key,val
        if (.not. associated(root)) then
            root => malloc_node(key,val)
            return
        end if
        
        node => root
        do
            if (key < node%key) then
                if (.not. associated(node%c_left)) then
                    node%c_left => malloc_node(key,val)
                    exit
                end if
                node => node%c_left
            else if (key > node%key) then
                if (.not. associated(node%c_right)) then
                    node%c_right => malloc_node(key,val)
                    exit
                end if
                node => node%c_right
            else
                node%val = val
                exit
            end if
        end do
    end subroutine

    subroutine delete_key(root,key)
        type(bst_node),pointer:: root, node, parent,child
        integer(int64):: key

        node => root
        parent => null()

        do while(associated(node))
            if (key < node%key) then
                parent => node
                node => node%c_left
            else if (key > node%key) then
                parent => node
                node => node%c_right
            else
                if (associated(node%c_left) .and. associated(node%c_right)) then
                    call delete_two_child_node(root, node)
                else if (associated(node%c_left)) then
                    child => node%c_left
                    call delete_one_child_node(node, child)
                else if (associated(node%c_right)) then
                child => node%c_right
                    call delete_one_child_node(node, child)
                else
                    call delete_leaf(parent, root, node)
                end if
                exit
            end if
        end do
    end subroutine

    subroutine delete_leaf(parent, root, node)
        type(bst_node),pointer:: parent, root, node
        if (associated(parent)) then
            if (associated(parent%c_left,node)) then
                parent%c_left => null()
            else
                parent%c_right => null()
            end if
            deallocate(node)
        else
            deallocate(node)
            root => null()
        end if
    end subroutine

    subroutine delete_one_child_node(node, child)
        type(bst_node),pointer:: child, node
        node%key = child%key
        node%c_left => child%c_left
        node%c_right => child%c_right
        deallocate(child)
    end subroutine

    subroutine delete_two_child_node(root, node)
        type(bst_node),pointer:: root,node
        type(bst_node),pointer:: max,max_parent

        max => node%c_left
        max_parent => node
        do while(associated(max%c_right))
            max_parent => max
            max => max%c_right
        end do

        node%key = max%key

        if (associated(max%c_left)) then
            call delete_one_child_node(max,max_parent)
        else
            call delete_leaf(max_parent,root,max)
        end if
    end subroutine

    recursive subroutine print_bst_node(root, depth)
        type(bst_node),pointer:: root
        integer(int32),optional:: depth
        integer(int32):: i, d

        if (.not. associated(root)) return
        d=0
        if (present(depth)) d=depth
        call print_bst_node(root%c_right, d+1)
        do i=1,d
            write(*,'(a)',advance='no') ' '
        end do
        print('(a,1x,a)'), 'key', root%key
        call print_bst_node(root%c_left, d+1)
    end subroutine
end module

module bst_mod
    use,intrinsic :: iso_fortran_env
    use bst_node_mod
    implicit none
    type bst
        type(bst_node),pointer:: root => null()
        contains
        procedure:: append => append_bst
        procedure:: del => delete_bst
        procedure:: has => has_key_bst
        procedure:: val => val
        procedure:: print => print_bst
    end type

contains
    subroutine append_bst(self, key, val)
        class(bst):: self
        integer(int64):: key,val
        call add_node(self%root,key,val)
    end subroutine

    subroutine delete_bst(self, key)
        class(bst):: self
        integer(int64):: key
        call delete_key(self%root, key)
    end subroutine

    function has_key_bst(self, key) result(ret)
        class(bst):: self
        integer(int64):: key
        logical:: ret
        
        ret = has_key(self%root, key)
    end function

    function val(self, key) result(ret)
        class(bst):: self
        integer(int64):: key, ret
        ret = get_val(self%root, key)
    end function

    subroutine print_bst(self)
        class(bst):: self
        call print_bst_node(self%root)
    end subroutine
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*,ans(i)
    end do

contains
    function solve(n,a,b,c,d) result(ret)
        use deque_mod
        use bst_mod
        integer(int64):: n,a,b,c,d
        integer(int64):: nval, nnum, hd, ld
        integer(int64):: ret,h_div,l_div,v
        type(deque):: num
        type(bst):: appear
        call num%init()
        call num%append(n)
        call appear%append(n,0_8)

        do while (num%remain())
            nnum = num%pop()
            nval = appear%val(nnum)
            ! print*, nnum, nval
            l_div = nnum/2
            h_div = l_div
            if (mod(nnum,2_8) /= 0) h_div=h_div+1
            h_div = ceiling(dble(nnum)/2d0, kind=int64)
            l_div = int(dble(nnum)/2d0, kind=int64)
            hd = 2*h_div - nnum
            if (dble(a+hd*d) < dble(nnum-h_div)*dble(d)) then
                v = nval+a+hd*d
            else
                v = nval+d*(nnum-h_div)
            end if
            call calc(appear, num, h_div, v)
            ld = nnum - 2*l_div
            if (l_div == 0) then
                if (.not. appear%has(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                else if (nval+ld*d < appear%val(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                end if
            else
                if (dble(a+ld*d) < dble(nnum-l_div)*dble(d)) then
                    v = nval+a+ld*d
                else
                    v = nval+d*(nnum-l_div)
                end if
                call calc(appear, num, l_div, v)
            end if

            l_div = nnum/3
            h_div = l_div
            if (mod(nnum,3_8) /= 0) h_div=h_div+1
            hd = 3*h_div - nnum
            if (dble(b+hd*d) < dble(nnum-h_div)*dble(d)) then
                v = nval+b+hd*d
            else
                v = nval+d*(nnum-h_div)
            end if
            call calc(appear, num, h_div, v)
            ld = nnum - 3*l_div
            if (l_div == 0) then
                if (.not. appear%has(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                else if (nval+ld*d < appear%val(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                end if
            else
                if (dble(b+ld*d) < dble(nnum-l_div)*dble(d)) then
                    v = nval+b+ld*d
                else
                    v = nval+d*(nnum-l_div)
                end if
                call calc(appear, num, l_div, v)
            end if

            l_div = nnum/5
            h_div = l_div
            if (mod(nnum,5_8) /= 0) h_div=h_div+1
            hd = 5*h_div - nnum
            if (dble(c+hd*d) < dble(nnum-h_div)*dble(d)) then
                v = nval+c+hd*d
            else
                v = nval+d*(nnum-h_div)
            end if
            call calc(appear, num, h_div, v)
            ld = nnum - 5*l_div
            ! print*, '5', hd, nnum+c+hd*d, ld, nval+c+ld*d
            if (l_div == 0) then
                if (.not. appear%has(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                else if (nval+ld*d < appear%val(l_div)) then
                    call appear%append(l_div, nval+ld*d)
                end if
            else
                if (dble(c+ld*d) < dble(nnum-l_div)*dble(d)) then
                    v = nval+c+ld*d
                else
                    v = nval+d*(nnum-l_div)
                end if
                call calc(appear, num, l_div, v)
            end if
        end do

        ret = appear%val(0_8)
    end function

    subroutine calc(a,d,n,v)
        use bst_mod
        use deque_mod
        type(bst):: a
        type(deque):: d
        integer(int64):: n,v

        if (.not. a%has(n)) then
            call a%append(n, v)
            call d%append(n)
        else if (v < a%val(n)) then
            call a%append(n, v)
            call d%append(n)
        end if
    end subroutine
end program main