#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>
#include <cstdint>

typedef unsigned long long int llint;

llint solve(llint n, llint a, llint b, llint c, llint d){
  std::priority_queue<std::array<llint, 2> > pq;

  std::map<llint, llint> M;

  std::set<std::array<llint,2> > check;
  pq.push({-0, n});
  while(!pq.empty()){
    const auto top = pq.top();
    //std::cout << top[0] << " " << top[1] << std::endl;
    if(top[1]==0) return -top[0];
    pq.pop();

    // d
    if(top[1]==1){
      std::array<llint, 2> data = {top[0]-d, top[1]-1};
      if(check.find(data) == check.end()){
	pq.push(data);
	check.insert(data);
      }
    }
    
    // a
    if(top[1]<2) continue;
    llint tmp = top[1]/2;
    llint amari = top[1]%2;
    llint added_cost = a+amari*d;
    if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
    std::array<llint, 2> data = {top[0]-added_cost, tmp };
    if(check.find(data) == check.end()){
      pq.push(data);
      check.insert(data);
    }
    if(amari){
      amari = 2-amari;
      tmp = tmp+1;
      added_cost = a+amari*d;
      if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
      data = {top[0]-added_cost, tmp };
      if(check.find(data) == check.end()){
	pq.push(data);
	check.insert(data);
      }
    }

    // b
    if(top[1]<3) continue;
    tmp = top[1]/3;
    amari = top[1]%3;
    added_cost = b+amari*d;
    if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
    data = {top[0]-added_cost, tmp };
    if(check.find(data) == check.end()){
      pq.push(data);
      check.insert(data);
    }
    if(amari){
      amari = 3-amari;
      tmp = tmp+1;
      added_cost = b+amari*d;
      if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
      data = {top[0]-added_cost, tmp };
      if(check.find(data) == check.end()){
	pq.push(data);
	check.insert(data);
      }
    }
    
    // c
    if(top[1]<5) continue;
    tmp = top[1]/5;
    amari = top[1]%5;
    added_cost = c+amari*d;
    if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
    data = {top[0]-added_cost, tmp };
    if(check.find(data) == check.end()){
      pq.push(data);
      check.insert(data);
    }    
    if(amari){
      amari = 5-amari;
      tmp = tmp+1;
      added_cost = c+amari*d;
      if(top[1]-tmp < added_cost/1.0/d) added_cost = (top[1]-tmp)*d;
      data = {top[0]-added_cost, tmp };
      if(check.find(data) == check.end()){
	pq.push(data);
	check.insert(data);
      }
    }
  }

  return -1;
  
  /**
  
  pq.push({-d, 1});
  while(!pq.empty()){
    auto top = pq.top();
    if(top[1]==n) return -top[0]; 
    pq.pop();

    // a
    auto next = top;
    next[0] = top[0]-a;
    next[1] = top[1]*2;
    pq.push(next);
    
    // b
    next[0] = top[0]-b;
    next[1] = top[1]*3;
    pq.push(next);
    // c
    next[0] = top[0]-c;
    next[1] = top[1]*5;
    pq.push(next);
    // d
    next[0] = top[0]-std::abs(n-top[1])*d;
    next[1] = n;
    pq.push(next);
    next[0] = top[0]-d;
    next[1] = top[1]+1;
    pq.push(next);
    next[0] = top[0]-d;
    next[1] = top[1]-1;
    pq.push(next);

  }
  **/

  return -1;
}

int main(void){
  int t;
  std::cin >> t;
  for(int i=0; i<t; i++){
    llint n, a, b, c, d;
    std::cin >> n >> a >> b >> c >> d;
    llint ret = solve(n, a, b, c, d);
    std::cout << ret << std::endl;
  }
  return 0;
}


Measured memory_bytes: 10828