#include<stdio.h>
#include<string.h> //strcmp、strncmp関数を使うために必要
     
int main(void)
{
    unsigned long i, n, t, a, b, c ,d,tmp,ans;
    
    scanf("%lu",&t);

    for(i=0;i<t;i++){
        scanf("%lu%lu%lu%lu%lu",&n,&a,&b,&c,&d);
        ans=d;
        tmp=n;
        while(1){
            if(tmp%5==0){
                tmp=tmp/5;
                ans+=c;
            }else if(tmp%5!=0||tmp<5){
            break;
            }
        }
        while(1){
            if(tmp%3==0){
                tmp=tmp/3;
                ans+=b;
            }else if(tmp%3!=0||tmp<3){
            break;
            }

        }
        while(1){
            if(tmp%2==0){
                tmp=tmp/2;
                ans+=a;
            }else if(tmp%2!=0||tmp<2){
            break;
            }
        }
        if(tmp!=0){
            for(;tmp==0;tmp--){
                ans+=d;
            }
        }

        printf("%lu",ans);
    }
      return 0;
}