program main
    implicit none
    integer(8) t
    integer(8), allocatable, dimension(:) :: n, a, b, c, d
    integer(8) i,j,k,l,m
    real(8) grada, gradb, gradc, minmum 
    integer(8) na, nb, nc, nd, flag, step
    integer(8) maxa, maxb, maxc
    real(8) ln2, ln3, ln5
    integer(8) temp, coin, cost, cost_min
    integer(8) na_min, nb_min, nc_min

    read(*,*) t
    allocate(n(t))
    allocate(a(t))
    allocate(b(t))
    allocate(c(t))
    allocate(d(t))

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

    temp = 0
    coin = 0
    
    ln2 = log(2.0)
    ln3 = log(3.0)
    ln5 = log(5.0)
    na = 0
    nb = 0
    nc = 0


    flag = 0
    temp = temp + 1
    
    do i = 1, t
    
        temp = 2
        maxa = 0
        do while(n(i) > temp)
            maxa = maxa + 1
            temp = temp*2
        end do

        temp = 3
        maxb = 0
        do while(n(i) > temp)
            maxb = maxb + 1
            temp = temp*3
        end do

        temp = 5
        maxc = 0
        do while(n(i) > temp)
            maxc = maxc + 1
            temp = temp*5
        end do

        maxa = maxa + 1
        maxb = maxb + 1
        maxc = maxc + 1
!        write(*,*) "max", maxa, maxb, maxc
        cost_min = n(i)*d(i)
        do j = 0, maxa
            na = j
            do k = 0, maxb
                nb = k
                do l = 0, maxc
                    nc = l
                    nd = abs(n(i)-(2**na)*(3**nb)*(5**nc)) + 1
                    cost = na*a(i) + nb*b(i) + nc*c(i) + nd*d(i)
                    if(cost < cost_min) then
                        cost_min = cost
                        na_min = na
                        nb_min = nb
                        nc_min = nc
                    end if
                end do
            end do
        end do

        na = na_min
        nb = nb_min
        nc = nc_min
        nd = abs(n(i)-(2**na)*(3**nb)*(5**nc)) + 1
        cost = na*a(i) + nb*b(i) + nc*c(i) + nd*d(i)

!        write(*,*) na, nb, nc, nd, cost
        write(*,*) cost
    end do

end program

