#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <deque>
#include <cmath>
using namespace std;

vector<string>split(string s, char delim){
  int len = s.length();
  string currStr = "";
  vector<string>retVec;
  for(int i = 0;i<len;i++){
    char ch = s[i];
    if(ch==delim){
      retVec.push_back(currStr);
      currStr = "";
    }else{
      currStr += ch;
    }
  }
  retVec.push_back(currStr);
  return retVec;
}



vector<long long>strToLLVec(string s){
  int len = s.length();
  //  s = s.substr(1,len-2);
  vector<string>strVec = split(s,' ');
  vector<long long>retVec;
  for(int i=0;i<strVec.size();i++){
    stringstream ss;
    ss<<strVec[i];
    long long el;
    ss>>el;
    retVec.push_back(el);
  }
  return retVec;
}

class SearchNode{public:
  long long currC;
  long long currV;
};

class Coins{
public:

  
  long long getMinCoins(long long n, long long a, long long b, long long c, long long d){
    long long minCoins = 1000000000000000000LL;
    unordered_map<long long,long long>costMap;
    setupCostMap(n,a,b,c,d,costMap);
    unordered_map<long long,long long>::iterator it;
    for(it=costMap.begin();it!=costMap.end();it++){
      long long y = it->first;
      long long toYCost = getNStepCost(n,a,b,c,d,y);
      long long totCost = toYCost+costMap[y];
      if(totCost<minCoins){
	minCoins = totCost;
      }
    }
    return minCoins;
  }

  long long powLL(long long base,long long powVal){
    long long retVal = 1LL;
    for(long long  i=0LL;i<powVal;i++){
      retVal *= base;
    }
    return retVal;
  }

  void setMap(long long n, long long a, long long b,long long c,long long d,long long x,long long y, long long z, long long stepVal ,unordered_map<long long,long long>&costMap){
    long long minC  = 1000000000000000000LL;
    if(stepVal==0LL){
      minC = 1000000000000000000LL;
    }else if(stepVal==1LL){
      minC = d;
    }else{
      long long cost1 = 1000000000000000000LL;
      double c1Dbl = (double)d*(double)stepVal;
      if(c1Dbl<(double)cost1){
	cost1 = d*stepVal;
      }
      long long cost2 = 1000000000000000000LL;
      long long powX = powLL(2LL,x);
      long long powY = powLL(3LL,y);
      long long powZ = powLL(5LL,z);      
      if((stepVal%2LL)==0LL){
	//long long nxt1 = ceil((double)n/powX/powY/powZ/2.0);
	//long long nxt2 = floor((double)n/powX/powY/powZ/2.0);
	cost2 = a + costMap[stepVal/2LL];
      }else if(stepVal>2LL){
	cost2 = d*(stepVal%2LL)+a +costMap[stepVal/2];
	cost2 = min(cost2,d*(2LL-stepVal%2LL)+a +costMap[stepVal/2+1LL]);
      }
      long long cost3 = 1000000000000000000;
      if((stepVal%3LL)==0LL){
	//long long nxt1 = ceil((double)n/powX/powY/powZ/3.0);
	//long long nxt2 = floor((double)n/powX/powY/powZ/3.0);
	cost3 = b+costMap[stepVal/3LL];
      }else if(stepVal>3LL){
	cost3 = (stepVal%3LL)*d+b+costMap[stepVal/3LL];
	cost3 = min(cost3,(3LL-stepVal%3LL)*d+b+costMap[stepVal/3LL+1LL]);
      }
      long long cost5 = 1000000000000000000;
      if((stepVal%5LL)==0LL){
	//long long nxt1 = ceil((double)n/powX/powY/powZ/5.0);
	//long long nxt2 = floor((double)n/powX/powY/powZ/5.0);
	cost5 = c + costMap[stepVal/5LL];
      }else if(stepVal>5LL){
	cost5 = d*(stepVal%5)+c + costMap[stepVal/5LL];
	cost5 = min(cost5,d*(5LL-stepVal%5)+c + costMap[stepVal/5LL+1LL]);	
      }
      //      cerr<<"setMap, c "<<c<<", stepVal/5 "<<stepVal/5LL<<endl;
      minC = min(cost1,cost2);
      minC = min(minC,cost3);
      minC = min(minC,cost5);
      //            cerr<<"setMat, cost1 "<<cost1<<", cost2 "<<cost2<<", cost3 "<<cost3<<", cost5 "<<cost5<<endl;
    }
    //        cerr<<"setMap, step "<<stepVal<<", minC "<<minC<<endl;
    costMap[stepVal] = minC;
  }

  long long getNStepCost(long long n,long long a,long long b,long long c,long long d, long long stepVal){
    long long retV = 1000000000000000000LL;
    long long cost2= 1000000000000000000LL;
    long long cost3= 1000000000000000000LL;
    long long cost5= 1000000000000000000LL;    
    long long cost1 = 1000000000000000000LL;
    double c1Dbl = (double)d*((double)n-stepVal);
    if(c1Dbl<(double)cost1){
      cost1 = d*(n-stepVal);
    }
    if(2LL*stepVal<n+2){
      double c2Dbl = (double)d*abs((double)n-2.0*stepVal)+(double)a;
      if(c2Dbl<(double)cost2){
	cost2 = d*abs(n-2LL*stepVal)+a;
      }
    }
    if(3LL*stepVal<n+3){
      double c3Dbl = (double)d*abs((double)n-3.0*stepVal)+(double)b;
      if(c3Dbl<(double)cost3){
	cost3 = d*abs(n-3LL*stepVal)+b;
      }
    }
    if(5LL*stepVal<n+5){
      double c5Dbl = (double)d*abs((double)n-5.0*stepVal)+(double)c;
      if(c5Dbl<(double)cost5){
	cost5 = d*abs(n-5LL*stepVal)+c;
      }
    }
    //    cerr<<"cost1 "<<cost1<<", cost2 "<<cost2<<", cost3 "<<cost3<<", cost5 "<<cost5<<endl;
    retV = min(cost3,cost5);
    retV = min(retV,cost2);
    retV = min(retV,cost1);    
    //       cerr<<"getNStepCost, step "<<stepVal<<", retV "<<retV<<endl;
    return retV;
  }
  
  void setupCostMap(long long n, long long a, long long b, long long c, long long d, unordered_map<long long, long long>&costMap){
    for(long long x = 60LL;x>=0LL;x--){
      long long powX = powLL(2LL,x);      
      for(long long y=38LL;y>=0LL;y--){
      long long powY = powLL(3LL,y);	
	for(long long z=26LL;z>=0LL;z--){
	  long long powZ = powLL(5LL,z);      	  
	  //long long den = powLL(2LL,x)*powLL(3LL,y)*powLL(5LL,z);
	  //	  cerr<<"setupcostmap, x "<<x<<", y "<<y<<", z "<<z<<endl;
	  long long step1Val = (((n/powX)/powY)/powZ);//like floor
	  long long step2Val = (((n/powX)/powY)/powZ);
	  if(step2Val*powX*powY*powZ<n)step2Val++;  //like ceil
	  if(costMap.find(step1Val)==costMap.end()){
	    setMap(n,a,b,c,d,x,y,z,step1Val,costMap);
	  }
	  if(costMap.find(step2Val)==costMap.end()){	  
	    setMap(n,a,b,c,d,x,y,z,step2Val,costMap);
	  }
	}
      }
    }
  }
  
};

int main(int argc, const char*argv[]){
  Coins coinObj;
  string tLn;
  getline(cin,tLn);
  int t = atoi(tLn.c_str());
  for(int i=0;i<t;i++){
    string inLn;
    getline(cin,inLn);
    vector<long long>inVec = strToLLVec(inLn);
    long long n = inVec[0];
    long long a = inVec[1];
    long long b = inVec[2];
    long long c = inVec[3];
    long long d = inVec[4];
    long long minCoins = coinObj.getMinCoins(n,a,b,c,d);
    cout<<minCoins<<endl;
  }
  return 0;
}


Measured memory_bytes: 4164