#include <stdio.h>
#include <string.h>

int goal,x2,x3,x5,plus1;
int loop(unsigned long long int now,unsigned long long int money,int mode);
unsigned long long int ans;

int main(void){
    int T;
    scanf("%d",&T);
    int mode=0;
    for(int i=0;i<T;i++){
        scanf("%d %d %d %d %d",&goal,&x2,&x3,&x5,&plus1);
        ans=200000000000000;
        loop(goal,0,mode);
        printf("%llu\n",ans);
    }
    
}

int loop(unsigned long long int now,unsigned long long int money,int mode){
    //printf("%llu %llu\n",now,money);
    if(now==0){
        //printf("------%llu %llu\n",ans,money);
        if(money<ans){
            ans=money;
        }
        return 0;
    }
    
    if(now%2==0){
        //printf("/2 %llu %llu\n",now,money+x2);
        loop(now/2,money+x2,0);
    }

    if(now%3==0){
        //printf("/3 %llu %llu\n",now,money+x3);
        loop(now/3,money+x3,0);
    }
    
    if(now%5==0){
        //printf("/5 %llu %llu\n",now,money+x5);
        loop(now/5,money+x5,0);
    }
    if(mode==1 && now!=1){
    if(now%2 != 0 && now%3 != 0  && now%5 != 0 ){
    //printf("+1 %llu %llu\n",now,money+plus1);
    loop(now+1,money+plus1,1);
    }
    }
    
    if(now%2 != 0 && now%3 != 0  && now%5 != 0){
    if(mode!=1){
    //printf("-1 %llu %llu\n",now,money+plus1);
    loop(now-1,money+plus1,-1);
    }
    }
    return 0;
}