PROGRAM g44a

IMPLICIT NONE
INTEGER :: T, x, i
INTEGER, ALLOCATABLE :: N(:), A(:), B(:), C(:), D(:), Z(:)

READ *, T

ALLOCATE (N(1:T))
ALLOCATE (A(1:T))
ALLOCATE (B(1:T))
ALLOCATE (C(1:T))
ALLOCATE (D(1:T))
ALLOCATE (Z(1:T))

DO i = 1, T
 READ *, N(i), A(i), B(i), C(i), D(i)

x = 0
Z(i) = 0

DO
IF(N(i) == x) THEN 
EXIT
ELSE IF(N(i) < x) THEN
 x = x - 1
 Z(i) = Z(i) + D(i)
ELSE IF(x > N(i) .AND. N(i) <= 2 * x) THEN
 IF(D(i) * (N(i) - 2 * x) + A(i) < D(i) * (N(i) - x)) THEN
  x = x + 1
  Z(i) = Z(i) + D(i)
 ELSE
  x = x * 2
  Z(i) = Z(i) + A(i)
 END IF
ELSE IF(2 * x > N(i) .AND. N(i) <= 3 * x) THEN
 IF (D(i) * (N(i) - 3 * x) + B(i) < D(i) * (N(i) - 2 * x) + A(i)) THEN
   x = x * 3
   Z(i) = Z(i) + B(i)
 ELSE IF(D(i) * (N(i) - 3 * x) + B(i) < D(i) * (N(i) - x)) THEN
   x = x * 2
   Z(i) = Z(i) + A(i)
ELSE
 x = x + 1
 Z(i) = Z(i) + D(i)
 END IF
ELSE
 IF(D(i) * (N(i) - 5 * x) + C(i) < D(i) * (N(i) - 3 * x) + B(i)) THEN
  x = x * 5
  Z(i) = Z(i) + C(i)
 ELSE IF(D(i) * (N(i) - 5 * x) + C(i) < D(i) * (N(i) - x)) THEN
  IF(D(i) * (N(i) - 5 * x) + C(i) > D(i) * (N(i) - x)) THEN
   x = x + 1
   Z(i) = Z(i) + D(i)
  ELSE IF(D(i) * (N(i) - 3 * x) + B(i) < D(i) * (N(i) - 2 * x) + A(i)) THEN
   x = x * 3
   Z(i) = Z(i) + B(i)
  ELSE IF(D(i) * (N(i) - 3 * x) + B(i) < D(i) * (N(i) - x)) THEN
   x = x * 2
   Z(i) = Z(i) + A(i)
  END IF
 ELSE
  x = x + 1
  Z(i) = Z(i) + D(i)
 END IF
END IF

END DO

PRINT *, Z(i)
END DO

END PROGRAM g44a