LINK：Pay to Win
自闭了 比赛的时候推出来正解了 以为复杂度不对 写完扔了 没拿map存状态就扔了23333...
一个T点：在更新map的时候 >不要写成>= 不然会徒劳的增加复杂度 被这个东西坑了好几次了。
思路：如果直接从1到n这样增加 很茫然 不知道要乘什么。
容易想到倒着做 从n到1这样。这样每次就知道到底可以除谁。
容易想到 x-w/d比x/d-w 优。
所以每次先考虑除以什么 如果要除以2 那么显然应该是2的倍数 3,5同理。
然后用map存状态 可以发现总状态量是1e5的 所以可以通过。
const ll MAXN=100010;
ll T;
ll n,A,B,C,D,ans;
map<ll,ll>H;
priority_queue<pii>q;
inline void gx(ll x,ll w)
{
if(w>=ans)return;
if(H.find(x)==H.end())H[x]=w,q.push(mk(x,-w));
else
{
if(w>=H[x])return;
H[x]=w;q.push(mk(x,-w));
}
}
signed main()
{
//freopen("1.in","r",stdin);
get(T);
while(T--)
{
get(n);get(A);get(B);get(C);get(D);
H.clear();q.push(mk(n,0));
ans=INF;H[n]=0;
int cnt=0;
while(q.size())
{
ll x=q.top().F;
ll w=-q.top().S;
q.pop();
if(w>ans)continue;
if(H[x]!=w)continue;
//考虑直接减到0
if(INF/D>x)ans=min(ans,D*x+w);
if(x%2)gx(x/2,w+D+A),gx(x/2+1,w+D+A);
else gx(x/2,w+A);
if(x%3)gx(x/3,w+x%3*D+B),gx(x/3+1,w+(3-x%3)*D+B);
else gx(x/3,w+B);
if(x%5)gx(x/5,w+x%5*D+C),gx(x/5+1,w+(5-x%5)*D+C);
else gx(x/5,w+C);
//put(++cnt);
}
putl(ans);
}
return 0;
}