#include <stdio.h>
int main(){
	long T,N,A,B,C,D;
	scanf("%d",&T);
	for(int i=0;i<T;i++){
	    scanf("%d %d %d %d %d",&N,&A,&B,&C,&D);
		long x = 0,count = 0;
		long enzan[5];
		while(x != N){
			enzan[0] = x * 2;
			enzan[1] = x * 3;
			enzan[2] = x * 5;
			enzan[3] = x + 1;
			enzan[4] = x - 1;
			
			for(int j=0;j<5;j++){
			    enzan[j] = N - enzan[j];
			}
			
			int min = 0,min_n;
			for(int j=0;j<5;j++){
			    if(j == 0){
			        min = enzan[0];
			        min_n = 0;
			    }
				if(enzan[j] < min){
					min = enzan[j];
					min_n = j;
				}
			}
			if(min_n == 0){
				x *= 2;
				count += A;
			}
			if(min_n == 1){
				x *= 3;
				count += B;
			}
			if(min_n == 2){
				x *= 5;
				count += C;
			}
			if(min_n == 3){
				x += 1;
				count += D;
			}
			if(min_n == 4){
				x -= 1; 
				count += D;
			}
		}
		printf("%d\n",count);
	}
}