program main
        implicit none
        integer :: A, B, C, D, N, T, i, j, k, co, minco
        read(*,*) T 
        do k=1, T
                read(*,*) N, A, B, C, D
                co = 0
                minco = 0

                do j=1,60
                        if (N == 0) then
                                exit
                        end if
                        do i=1, 5
                                if (N/5==0 .and. i==1) then
                                        N = N/5
                                        co = co + C
                                        exit
                                else if (N/3==0 .and. i==2) then
                                        N = N/3
                                        co = co + B
                                        exit
                                else if (N/2==0 .and. i==3) then
                                        N = N/2
                                        co = co + A
                                        exit
                                else if (N/2/=0 .and. i==4) then
                                        N = N+1
                                        co = co + D
                                        exit
                                else if (N/2/=0 .and. i==5) then
                                        N = N-1
                                        co = co + D 
                                        exit
                                else
                                        cycle
                                end if
                        end do
                end do
                if (co < minco) then
                        minco = co
                end if
                write(*,*) minco
        end do
end program main