#include<bits/stdc++.h> #define int long long using namespace std; int s[16]; int m,a1,a2,b1,b2; int ans; int t; signed main(){ s[0]=1; for (int i=1;i<=15;i++){ s[i]=s[i-1]*i; } int tsknum; cin>>tsknum; cin>>t; while (t--){ cin>>m>>a1>>b1>>a2>>b2; ans=0x3f3f3f3f3f3f3f3f; for (int i=0;i<4096;i++){ int x=m,res=0; for (int j=0;j<12;j++){ if (i>>j&1){ x-=s[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; } return 0; }