Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])


Fixed submission:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Buggy python submission (verdict: Runtime Error):
import sys
from numba import njit
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False
	@njit
	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])


Fixed submission:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Fixed submission:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//4)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//4 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Fixed submission:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])