#include<bits/stdc++.h> #define int long long using namespace std; int fact[20]; void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar(); } void slv(){ int m,a1,a2,b1,b2; read(m),read(a1),read(b1),read(a2),read(b2); int ans=1e18; for(int i=0;i<4096;i++){ int x=m,res=0; for(int j=0;j<12;j++){ if(i>>j&1)x-=fact[j+3],res+=a1+b1*(j+3); } if(x<0)continue; for(int j=0;j<40;j++){ if(x>>j&1){ if(j==0)res+=min(a1+b1,a2); else if(j==1)res+=min(a1+2*b1,a2+b2); else res+=a2+b2*j; } } ans=min(ans,res); } cout<<ans<<endl; } signed main(){ fact[0]=1; for(int i=1;i<=15;i++)fact[i]=fact[i-1]*i; int id; read(id); int T; read(T); while(T--)slv(); return 0; }