#include<bits/stdc++.h> using namespace std; int id,t; long long m,a1,b1,a2,b2; long long ans=0; int c[20]; long long js(long long k){ long long p=1; for(int i=1;i<=k;i++)p*=i; if(k==0) return 0; else return p; } long long jss(long long k){ long long p=0,u=0; while(k!=0){ if(k%2==1){ p+=a2+b2*u; if(u==0&&c[1]==1) return 1e18; if(u==1&&c[2]==1) return 1e18; } u++; k/=2; } return p; } void dfs(long long m,int k1,long long z){ if(m<0) return; //cout<<m<<" "; ans=min(ans,z+jss(m)); for(int i=k1;i;i--) c[i]=1,dfs(m-js(i),i-1,z+a1+b1*i),c[i]=0; } int main(){ cin>>id>>t; while(t--){ cin>>m>>a1>>b1>>a2>>b2; ans=1e18; dfs(m,14,0); cout<<ans<<endl; } }