//これじゃ素因数分解できるやつしか解けないし最小かも判断できない…
#include<iostream>
using namespace std;

int main(){
  int t,n,a,b,c,d,i,j,ax,bx,cx,dx ;
  cin >> t ;
  for (i=1;i<=t;i++){
  	cin >> n >> a >> b >> c >>d;
    ax=0;
    bx=0;
    cx=0;
    dx=0;
    	while(n % 2== 0) {
      		ax++;
      		n /= 2;
    	}
    	while(n % 3== 0) {
      		bx++;
      		n /= 3;
    	}
    	while(n % 5== 0) {
      		cx++;
      		n /= 5;
    	}
  		if(n == 1){
    		cout << a*ax+b*bx+c*cx+d*dx+d <<endl;
  		}
  	} 
  }

