#include<bits/stdc++.h> using namespace std; #define int long long const int N=20; int id,T,m,a,b,c,d,fac[N],ans; bool ch[N]; void cal(){ int cnt=0;int mm=m; // cout<<"???"<<endl; // for(int i=1;i<=14;i++)cout<<ch[i]<<" ";cout<<endl; for(int i=1;i<=14;i++){ if(ch[i]){mm-=fac[i];cnt+=a+i*b;} } if(mm<0){return;} if(mm==0){ans=min(ans,cnt);return;} // cout<<endl; int k=__lg(mm);//cout<<mm<<">>>>>"<<k<<endl; for(int i=k;i>=0;i--){ if((1<<i)&mm){ if(ch[1]&&i==0)return; if(ch[2]&&i==1)return; mm-=(1<<i);cnt+=c+i*d; } }//cout<<endl; // cout<<ans<<" "; ans=min(ans,cnt); // cout<<cnt<<" "<<ans<<endl; } void dfs(int i){ if(fac[i]>m){cal();return;} ch[i]=0;dfs(i+1); ch[i]=1;dfs(i+1); } int read(){ char c=getchar();int d=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){d=d*10+c-'0';c=getchar();} return d; } signed main(){ fac[0]=1;for(int i=1;i<=15;i++)fac[i]=fac[i-1]*i; id=read();T=read(); while(T--){ m=read(); a=read();b=read();c=read();d=read(); for(int i=1;i<=14;i++)ch[i]=0; ans=1e17;dfs(1); printf("%lld\n",ans); } return 0; }