1 #include <queue>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 #define ll long long
 7 using namespace std;
 8 const ll N=1000010,inf=2e18;
 9 typedef pair<ll,int>node; 
10 priority_queue<node,vector<node>,greater<node> >Q;  
11 struct edge {int to,from;ll w;}e[N];
12 ll w,ans,k,a,b,c,d,dis[5][N];
13 int T,cnt,head[N];
14 void insert(int x,int y,ll w)
15 {
16     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].w=w;
17     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].w=w;
18 }
19 void dijkstra(ll s)
20 {
21     for (ll i=0;i<=4;i++) for (ll j=0;j<w;j++) dis[i][j]=inf;
22     Q.push(make_pair(0ll,s));
23     while (!Q.empty())
24     {
25         ll x=Q.top().first;int y=Q.top().second; Q.pop();
26         if (x>dis[y][x%w]) continue;
27         for (int i=head[y];i;i=e[i].from)
28         {
29             ll xx=x+e[i].w;
30             if (dis[e[i].to][xx%w]>xx) dis[e[i].to][xx%w]=xx,Q.push(make_pair(xx,e[i].to));
31         }
32     }
33 }
34 int main()
35 {
36     scanf("%d",&T);
37     while (T--)
38     {
39         memset(head,-1,sizeof(head)),scanf("%lld%lld%lld%lld%lld",&k,&a,&b,&c,&d),ans=inf,cnt=0;
40         w=2*min(a,b);
41         insert(1,2,a),insert(2,3,b),insert(3,4,c),insert(1,4,d),dijkstra(2);
42         for (ll i=0;i<w;i++) if (k<=dis[2][i]) ans=min(ans,dis[2][i]); else ans=min(ans,dis[2][i]+((k-dis[2][i]+w-1)/w)*w);
43         printf("%lld\n",ans);
44     }
45 }