#include <stdio.h>

#define NUM 100000

int main(void){

        int a[NUM],b[NUM],c[NUM],d[NUM],t;
        int n[NUM];

        scanf("%d",&t);

        int coin[10000] = {0};

for(int i=0;i<t;i++){
        scanf("%d%d%d%d%d",&n[i],&a[i],&b[i],&c[i],&d[i]);

while(n[i]>0){

if(n[i]%5 == 0){ 
        n[i] = n[i]/5;
        coin[i] = coin[i] + a[i];
}else if(n[i]%3 == 0){ 
        n[i] = n[i]/3;
        coin[i] = coin[i] + b[i];
}else if(n[i] % 2 == 0){ 
        n[i] = n[i]/2;
        coin[i] = coin[i] + c[i];
}else{
        n[i] = n[i] - 1;
        coin[i] = coin[i] + d[i];
}
}
printf("%d\n",coin[i]);
}
return 0;
}

