#include<bits/stdc++.h> using namespace std; const int N = 60; #define ll long long int id,T,c[N]; ll m,a,b,a_2,b_2,pre[N],ans; int main(){ //freopen("powerer.in","r",stdin); //freopen("powerer.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>id>>T; while(T--){ cin>>m>>a>>b>>a_2>>b_2; ans=1e18; ll x=1; int bz=0; for(int i=1;;i++){ x=x*(ll)i; if(x>m){ break; } bz=i; pre[i]=x; } for(int i=0;i<(1<<bz);i++){ ll cnt=0,w=0; bool flag=false; bool flag2=false; for(int j=1;j<=bz;j++){ if((1<<(j-1))&i){ if(j==1) flag=true; if(j==2) flag2=true; cnt=cnt+pre[j]; w=w+a+b*j; } } int num=0; ll tmp=m-cnt; if(tmp<0){ continue; } if(tmp==0){ ans=min(ans,w); continue; } while(tmp){ if(tmp&1){ c[++num]=1; } else{ c[++num]=0; } tmp=tmp>>1; } if(c[1]==1&&flag){ continue; } if(c[2]==1&&flag2&&num>=2){ continue; } for(int j=1;j<=num;j++){ if(c[j]==1){ w=w+a_2+(j-1)*b_2; } } ans=min(ans,w); } cout<<ans<<endl; } return 0; }