#include<stdio.h>
int main(void){
int t;
  scanf("%d",&t);
  long long n[t];
  long a[t],b[t],c[t],d[t];
  for(int i=0;i<t;i++){
  scanf("%lld%ld%ld%ld%ld",&n[i],&a[i],&b[i],&c[i],&d[i]);
  }
  long long count=0;
  long long x,min=100000000000000000;
  for(int i=0;i<t;i++){
	x=n[i];
    for(int j=0;j<=4;j++){
	x-=j;		//スタートx-j(0-4)それぞれ比較
      if(x<=0)break;
    if(j!=0)count+=d[i];
      while(x!=0){if(x%5!=0&&x%3!=0&&x%2!=0){
        			x-=1;
        			count+=d[i];
      }
                  else if(x%5==0){
                    x/=5;
                    count+=c[i];
                  }
                  else if(x%3==0){
					x/=3;
                    count+=b[i];
                  }
                  else if(x%2==0){
				x/=2;
                    count+=a[i];
                  }
                 }
      if(count<min)min=count;
      count=0;
    }
    printf("%lld\n",min);
  }
  return 0;
}