#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
#define INF 20000000000000
#define PI 3.14159265359
#define ull unsigned long long

int main(){
    ull t,n[11],a[11],b[11],c[11],d[11],i,num=0,coin=0,j,hyouka[3]={},tmp=0;
    scanf("%lld",&t);
    for (i=0; i<t; i++) scanf("%lld%lld%lld%lld%lld",&n[i],&a[i],&b[i],&c[i],&d[i]);
    for (j=0; j<t; j++) {
        num=0;coin=0;tmp=n[j];
        while (num!=n[j]) {
            if (num==0){
                num++;
                coin+=d[j];
            }
            else if(num==n[j]-1){
                num++;
                coin+=d[j];
            }
            else if(num==n[j]+1){
                num--;
                coin+=d[j];
            }else{
                hyouka[0]=(tmp/5)*c[j];
                hyouka[1]=(tmp/3)*b[j];
                hyouka[2]=(tmp/2)*a[j];
                if (hyouka[0]==0) hyouka[0]=INF;
                if (hyouka[1]==0) hyouka[1]=INF;
                if (hyouka[2]==0) hyouka[2]=INF;
                if (hyouka[0]<hyouka[1]&&hyouka[0]<hyouka[2]){num*=5;tmp/=5;coin+=c[j];}
                else if (hyouka[1]<hyouka[0]&&hyouka[1]<hyouka[2]){num*=3;tmp/=3;coin+=b[j];}
                else if (hyouka[2]<hyouka[1]&&hyouka[2]<hyouka[0]){num*=2;tmp/=2;coin+=a[j];}
                else {num++;coin++;}
            }
        }
        printf("%lld\n",coin);
    }
    
    return 0;
}

