import std;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		long n, a, b, c, d;
		readf !(" %s %s %s %s %s") (n, a, b, c, d);
		long [long] costs;
		costs[2] = a;
		costs[3] = b;
		costs[5] = c;

		long [long] fSaved;
		fSaved[1] = d;

		long f (long v)
		{
			if (v !in fSaved)
			{
				long ans = long.max;
				if (d * v / v == d)
				{
					ans = d * v;
				}
				foreach (cur, cost; costs)
				{
					if (cur <= v)
					{
						auto rem = v % cur;
						ans = min (ans, cost +
						    d * rem + f (v / cur));
						if (rem > 0)
						{
							ans = min (ans, cost +
							    d * (cur - rem) +
							    f (v / cur + 1));
		                        	}
					}
				}
				fSaved[v] = ans;
			}
	                return fSaved[v];
		}

		writeln (f (n));
	}
}
