using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int T = int.Parse(Console.ReadLine());
		for(var t=0;t<T;t++){
			string[] str = Console.ReadLine().Split();
			long N = long.Parse(str[0]);
			long A = long.Parse(str[1]);
			long B = long.Parse(str[2]);
			long C = long.Parse(str[3]);
			long D = long.Parse(str[4]);
			long n = 1;
			long c = D;
			var dic = new Dictionary<long,long>();
			dic[N] = D;
			long ans = (long)Math.Pow(10,18);
			var list = new List<long>();
			list.Add(N);
			while(list.Count>0){
				//if(t>=3){
	            //  	Console.Error.WriteLine(list.Count+" "+ans);
				//}
				var list2 = new List<long>(list);
				list.Clear();
				foreach(var i in list2){
					if(i%2==0){
						if(dic.ContainsKey(i/2)){
							if(dic[i]+A < dic[i/2]){
								dic[i/2] = dic[i]+A;
								if(i/2==1){
									ans = Math.Min(ans,dic[i/2]);
								}
								if(dic[i/2]<ans){
									list.Add(i/2);
								}
							}
						} else {
							dic[i/2] = dic[i]+A;
							if(i/2==1){
								ans = Math.Min(ans,dic[i/2]);
							}
							if(dic[i/2]<ans){
								list.Add(i/2);
							}
						}
					}
					if(i%3==0){
						if(dic.ContainsKey(i/3)){
							if(dic[i]+B < dic[i/3]){
								dic[i/3] = dic[i]+B;
								if(i/3==1){
									ans = Math.Min(ans,dic[i/3]);
								}
								if(dic[i/3]<ans){
									list.Add(i/3);
								}
							}
						} else {
							dic[i/3] = dic[i]+B;
							if(i/3==1){
								ans = Math.Min(ans,dic[i/3]);
							}
							if(dic[i/3]<ans){
								list.Add(i/3);
							}
						}
					}
					if(i%5==0){
						if(dic.ContainsKey(i/5)){
							if(dic[i]+C < dic[i/5]){
								dic[i/5] = dic[i]+C;
								if(i/5==1){
									ans = Math.Min(ans,dic[i/5]);
								}
								if(dic[i/5]<ans){
									list.Add(i/5);
								}
							}
						} else {
							dic[i/5] = dic[i]+C;
							if(i/5==1){
								ans = Math.Min(ans,dic[i/5]);
							}
							if(dic[i/5]<ans){
								list.Add(i/5);
							}
						}
					}
					if(i%30!=0){
						if(dic.ContainsKey(i+1)){
							if(dic[i]+D < dic[i+1]){
								dic[i+1] = dic[i]+D;
								if(i+1==1){
									ans = Math.Min(ans,dic[i+1]);
								}
								if(dic[i+1]<ans){
									list.Add(i+1);
								}
							}
						} else {
							dic[i+1] = dic[i]+D;
							if(i+1==1){
								ans = Math.Min(ans,dic[i+1]);
							}
							if(dic[i+1]<ans){
								list.Add(i+1);
							}
						}
					}
					if(i%30!=0){
						if(dic.ContainsKey(i-1)){
							if(dic[i]+D < dic[i-1]){
								dic[i-1] = dic[i]+D;
								if(i-1==1){
									ans = Math.Min(ans,dic[i-1]);
								}
								if(dic[i-1]<ans){
									list.Add(i-1);
								}
							}
						} else {
							dic[i-1] = dic[i]+D;
							if(i-1==1){
								ans = Math.Min(ans,dic[i-1]);
							}
							if(dic[i-1]<ans){
								list.Add(i-1);
							}
						}
					}
				}
			}
			int d = 0;
			for(var i=1;i<=18;i++){
				if(D>=Math.Pow(10,i)){
					d = i;
				}
			}
			foreach(var i in dic.Keys){
				int e = 0;
				for(var j=1;j<=18;j++){
					if(i>=Math.Pow(10,j)){
						e = j;
					}
				}
				int f = 0;
				for(var j=1;j<=18;j++){
					if(dic[i]>=Math.Pow(10,j)){
						f = j;
					}
				}
				if(e+d<=16 && f<=16 && (i-1)*D + dic[i] < ans){
					ans = (i-1)*D + dic[i];
				}
			}
			Console.WriteLine(ans);
		}
	}
}

Measured memory_bytes: 39772