#include <stdio.h>
#include <stdlib.h>

int ax(int a,int *x){
	*x *= 2;
   return *x;
}

int bx(int b,int *x){
	*x *= 3;
	return *x;
}

int cx(int c,int *x){
	*x *= 5;
	return *x;
}

int dx(int d,int *x,int n){
	if(*x<n){
		*x += 1;
	}
	else{
		*x -= 1;
	}
	return *x;
}
int main(void) {
	int T,N,A,B,C,D;

	scanf("%d",&T);
	if(T<1 || T>10){
		return 0;
	}

		int i;
	for(i=T ; i>0 ; i--){
	 scanf("%d %d %d %d %d",&N,&A,&B,&C,&D);
	    if(N<1 || N>1000000000000000000){
	 	   return 0;
	     }
	    if(A<1 || A>1000000000){
		   return 0;
	     }
	    if(B<1 || B>1000000000){
		   return 0;
	     }
	    if(C<1 || C>1000000000){
		   return 0;
         }
	    if(D<1 || D>1000000000){
		   return 0;
	     }

  int x=0,j=0;
  dx(D,&x,N);
 	 j += D;
  do{
	 if(x*2 < N && (N/(x * 2))*A <= (N/(x * 3))*B && (N/(x * 2))*A <= (N/(x * 5))*C && (N/(x * 2))*A <= (N-x)*D){
		 ax(A,&x);
		 j += A;
	 }
	 else if(x*5 < N && (N/(x * 3))*B <= (N/(x * 5))*C && (N/(x * 3))*B <= (N-x)*D){
		 bx(B,&x);
		 j += B;
	 }
	else if(x*5 < N && (N/(x * 5))*C <= (N-x)*D){
		cx(C,&x);
		j += C;
	}
	else{
		dx(D,&x,N);
		j += D;
	}
  }while(N != x);
  printf("%d\n",j);
 }
	return 0;
}
