CodeEff/ECCO huggingface dataset:
# Original solution
def bomb(x,y):
    s=M[y]
    if s[x]=="0":return
    M[y]=s[:x]+"0"+s[x+1:]
    R=[-3,-2,-1,1,2,3]
    for e in R:
        bomb(x+e,y)
        bomb(x,y+e)
    return

A=list(range(3,11))
M=["00000000000000" for i in range(14)]
z="000"
n=eval(input())
for i in range(n):
    s=input()
    for j in A:
        M[j]=z+input()+z
    x=eval(input())+2
    y=eval(input())+2
    bomb(x,y)
    print("Data %d:" %(i+1))
    for j in A:
        print(M[j][3:-3])

# Optimized solution
def bomb(x,y):
    s=M[y]
    if s[x]=="0":return
    M[y]=s[:x]+"0"+s[x+1:]
    R=[-3,-2,-1,1,2,3]
    for e in R:
        bomb(x+e,y)
        bomb(x,y+e)
    return

A=list(range(14))
B=list(range(3,11))
M=["0"*14 for i in A]
z="000"
n=eval(input())
for i in range(n):
    s=input()
    for j in B:
        M[j]=z+input()+z
    x=eval(input())+2
    y=eval(input())+2
    bomb(x,y)
    print("Data %d:" %(i+1))
    for j in B:
        print(M[j][3:-3])
# Original solution
a,b,c=list(map(int, input().split()))
d=0
for _ in range(60):
    if c<=d+a:
        print(c)
        break
    d+=a+b
    while c<=d:c+=60
else: print((-1))

# Optimized solution
a,b,c=list(map(int, input().split()))
d,e=0,60
for _ in range(e):
    if c<=d+a:
        print(c)
        break
    d+=a+b
    c+=(d+e-c)//e*e
else: print((-1))
# Original solution
def solve(a, b, c):
    l = 0; r = a;
    for t in range(114514):
        t = l // 60
        p = 60*t + c
        if l <= p <= r:
            print(p)
            exit()

        l = r + b
        r = l + a

    print((-1))

a, b, c = list(map(int, input().split()))
solve(a,b,c)

# Optimized solution
def solve(a, b, c):
    l = 0; r = a;
    for t in range(514):
        t = l // 60
        p = 60*t + c
        if l <= p <= r:
            print(p)
            exit()

        l = r + b
        r = l + a

    print((-1))

a, b, c = list(map(int, input().split()))
solve(a,b,c)
# Original solution
import sys
INF = (sys.maxsize)/3

def NumberofWindow(a_list, S):
	i = 0
	j = 0
	tmpS = a_list[0]
	res = 0
	while j < len(a_list)  :
		while tmpS <= S and i <len(a_list)-1:
			i += 1
			tmpS += a_list[i]
		if i == len(a_list)-1:
			if tmpS > S:
				res += i-j
			else:
				res += i-j+1
		else:
			res += i-j
		tmpS -=a_list[j]
		j += 1
	return res
		

def main():
	N, Q = list(map(int, input().split()))
	a_list = list(map(int, input().split()))
	x_list = list(map(int, input().split()))
	for x in x_list:
		print(NumberofWindow(a_list, x))

if __name__ == '__main__':
	main()

# Optimized solution
import sys
INF = (sys.maxsize)/3

def NumberofWindow(N, a_list, S):
	i = 0
	j = 0
	tmpS = a_list[0]
	res = 0
	while j < N  :
		while tmpS <= S and i <N-1:
			i += 1
			tmpS += a_list[i]
		if i == N-1:
			if tmpS > S:
				res += i-j
			else:
				res += i-j+1
		else:
			res += i-j
		tmpS -=a_list[j]
		j += 1
	return res
		

def main():
	N, Q = list(map(int, input().split()))
	a_list = list(map(int, input().split()))
	x_list = list(map(int, input().split()))
	'''
	f = open('DSL_3_C-in21.txt', 'r')
	N, Q = map(int, f.readline().split())
	a_list = map(int, f.readline().split())
	x_list = map(int, f.readline().split())
	'''
	for x in x_list:
		print(NumberofWindow(N, a_list, x))
if __name__ == '__main__':
	main()
# Original solution
import sys
INF = (sys.maxsize)/3

def NumberofWindow(N, a_list, S):
	i = 0
	j = 0
	tmpS = a_list[0]
	res = 0
	while j < N  :
		while tmpS <= S and i <N-1:
			i += 1
			tmpS += a_list[i]
		if i == N-1:
			if tmpS > S:
				res += i-j
			else:
				res += i-j+1
		else:
			res += i-j
		tmpS -=a_list[j]
		j += 1
	return res
		

def main():
	N, Q = list(map(int, input().split()))
	a_list = list(map(int, input().split()))
	x_list = list(map(int, input().split()))
	'''
	f = open('DSL_3_C-in21.txt', 'r')
	N, Q = map(int, f.readline().split())
	a_list = map(int, f.readline().split())
	x_list = map(int, f.readline().split())
	'''
	for x in x_list:
		print(NumberofWindow(N, a_list, x))
if __name__ == '__main__':
	main()

# Optimized solution
import sys
INF = (sys.maxsize)/3

def NumberofWindow(N, a_list, S):
	i = 0
	j = 0
	tmpS = a_list[0]
	res = 0
	for j in range(N) :
		while tmpS <= S and i <N-1:
			i += 1
			tmpS += a_list[i]
		if i == N-1:
			if tmpS > S:
				res += i-j
			else:
				res += i-j+1
		else:
			res += i-j
		tmpS -=a_list[j]
	return res
		

def main():
	N, Q = list(map(int, input().split()))
	a_list = list(map(int, input().split()))
	x_list = list(map(int, input().split()))
	'''
	f = open('DSL_3_C-in21.txt', 'r')
	N, Q = map(int, f.readline().split())
	a_list = (map(int, f.readline().split()))
	x_list = (map(int, f.readline().split()))
	'''
	for x in x_list:
		print(NumberofWindow(N, a_list, x))
if __name__ == '__main__':
	main()
# Original solution
from bisect import bisect
from itertools import accumulate

n, q = list(map(int, input().split()))
ac = list(accumulate(list(map(int, input().split()))))
anss = []
for x in map(int, input().split()):
    ans = 0
    prev = 0
    for l, a in enumerate(ac):
        r = bisect(ac, prev + x, l)
        ans += r - l
        prev = a
    anss.append(ans)

print(('\n'.join(map(str, anss))))

# Optimized solution
n, q = list(map(int, input().split()))
aa = list(map(int, input().split()))
anss = []
for x in map(int, input().split()):
    l = 0
    ans = 0
    _sum = 0
    for r, a in enumerate(aa):
        _sum += a
        while _sum > x:
            _sum -= aa[l]
            l += 1
        ans += r - l + 1
    anss.append(ans)

print(('\n'.join(map(str, anss))))
# Original solution
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
k=N()
s=input()
if len(s)<=k:
    print(s)
else:
    print(s[:k]+"...")


# Optimized solution
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
k=N()
s=input()
if len(s)<=k:
    print(s)
else:
    print(s[:k]+"...")
# Original solution
import bisect,collections,copy,heapq,itertools,math,string
import sys
sys.setrecursionlimit(1000000)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
K = I()
S = S()

if len(S) <= K:
    print(S)
    sys.exit()
else:
    li = "".join([S[0:K],"..."])
    print(li)

# Optimized solution
import sys
sys.setrecursionlimit(1000000)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
K = I()
S = S()

if len(S) <= K:
    print(S)
    sys.exit()
else:
    li = "".join([S[0:K],"..."])
    print(li)
# Original solution
import sys
input = sys.stdin.readline
k = int(eval(input()))
s = list(input().rstrip())
n = len(s)

if n <= k:
    print(("".join(s)))
else:
    ans = "".join(s[:k]) + "..."
    print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

k = int(eval(input()))
s = input().rstrip()
ans = s if len(s) <= k else s[:k] + "..."
print(ans)
# Original solution
MOD = 10**9 + 7

N = int(eval(input()))
S = input().rstrip()

is_left = [(i%2 == 0) ^ (x == "W") for i, x in enumerate(S)]

answer = 1
left = 0
for bl in is_left:
    if bl:
        left += 1
    else:
        answer *= left
        left -= 1


if left != 0:
    answer = 0
    
for i in range(1, N+1):
    answer *= i
    answer %= MOD

print(answer)

# Optimized solution
MOD = 10**9 + 7

N = int(eval(input()))
S = input().rstrip()

is_left = [(i%2 == 0) ^ (x == "W") for i, x in enumerate(S)]

answer = 1
left = 0
for bl in is_left:
    if bl:
        left += 1
    else:
        answer *= left
        left -= 1
        answer %= MOD

if left != 0:
    answer = 0
    
for i in range(1, N+1):
    answer *= i
    answer %= MOD

print(answer)
# Original solution
n,s=open(0)
n=int(n)
a=l=s[0]<'W'>s[-2]
r=f=0
for b,c in zip(s,s[1:-1]):f^=b==c;a=a*(max(1,n))*(l-r)**f%(10**9+7);n-=1;r+=f;l+=f^1
print((a*(l==r)))

# Optimized solution
n,s=open(0)
n=int(n)
a=l=s[0]<'W'>s[-2]
r=f=0
for b,c in zip(s,s[1:-1]):f^=b==c;a=a*(n<1or n)*(l-r)**f%(10**9+7);n-=1;r+=f;l+=f^1
print((a*(l==r)))
# Original solution
n,s=open(0)
a=i=1
l=0
for c in s:f=(c>'B')^i%2;l+=f;a=a*l**f*(i>int(n)or i)%(10**9+7);l-=f^1;i+=1
print((a*(l==1)))

# Optimized solution
n,s=open(0)
a=i=1
l=0
for c in s:f=(c>'B')^i%2;l+=f or-1;a=a*l**f*(i>int(n)or i)%(10**9+7);i+=1
print((a*(l==1)))
# Original solution
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    s = {(0, 0, 0)}.union(*({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b)))
    m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s)
    memo[n] = m
  return m

t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))


# Optimized solution
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)
    memo[n] = m
  return m

t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))
# Original solution
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      m = min(m, *(f(k) + abs(p * k - n) * d + c for k in (n // p, -(-n // p))))
    memo[n] = m
  return m

t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))


# Optimized solution
a = 2, 3, 5
 
def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)
    memo[n] = m
  return m
 
t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))
# Original solution
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + c or m)
    memo[n] = m
  return m

t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))


# Optimized solution
a = 2, 3, 5
 
def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)
    memo[n] = m
  return m
 
t = int(eval(input()))
for _ in range(t):
  n, *b, d = list(map(int, input().split()))
  memo = {0: 0, 1: d}
  print((f(n)))
# Original solution
import sys

divs = [2, 3, 5]

t = int(eval(input()))

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {}

    def dfs(x):
        if x in dp:
            return dp[x]

        # print(x, file=sys.stderr)

        if x == 0:
            dp[x] = 0
            return dp[x]

        ret = x * d
        for i in range(-4, 5):
            if x - i < 0:
                continue

            nx = x - i
            for cost, div in zip(costs, divs):
                if nx % div != 0 or nx // div >= x:
                    continue

                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)

        dp[x] = ret
        return ret

    print((dfs(n)))


# Optimized solution
divs = [2, 3, 5]

t = int(eval(input()))

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {0: 0}

    def dfs(x):
        if x in dp:
            return dp[x]

        ret = x * d

        for cost, div in zip(costs, divs):
            lx = x // div * div
            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d)

            if lx == x:
                continue
            lx += div
            if lx // div >= x:
                continue
            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)

        dp[x] = ret
        return ret

    print((dfs(n)))
# Original solution
t = int(eval(input()))

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print((calc(n)))


# Optimized solution
t = int(eval(input()))

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]
        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])
    return dp[x]

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {0: 0, 1: d}
    print((calc(n)))
# Original solution
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if dp[rem] <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))


# Optimized solution
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))
# Original solution
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))


# Optimized solution
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    div, m = divmod(rem, x)
                    if div:
                        stack.append((div, d*m+cost+y))
                    if m:
                        stack.append((div+1, d*(x-m)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))
# Original solution
import sys
sys.setrecursionlimit(10**8)
T=int(eval(input()))

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

for _ in range(T):
    N,A,B,C,D=list(map(int,input().split()))
    dic={}
    print((solve(N)))


# Optimized solution
T=int(eval(input()))
from functools import lru_cache

for _ in range(T):
    N,A,B,C,D=list(map(int,input().split()))
    @lru_cache(maxsize=None)  
    def solve(N):
        if N==0:
            return 0
        if N==1:
            return D
        tmp=N*D    
        if N%2==0:
            tmp=min(tmp,solve(N//2)+A)
        else:
            tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
        if N%3==0:
            tmp=min(tmp,solve(N//3)+B)
        else:
            b=N%3 
            tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
        if N%5==0:
            tmp=min(tmp,solve(N//5)+C)
        else:
            c=N%5
            tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
        return tmp

    print((solve(N)))
# Original solution
import sys
sys.setrecursionlimit(10**6)
T = int(eval(input()))
for _ in range(T):
	n, a, b, c, d = list(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]))


# Optimized solution
import sys
from heapq import heappush, heappop
T = int(eval(input()))
for _ in range(T):
	n, a, b, c, d = list(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]))
# Original solution
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=k*d
    s=min(s,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(eval(input()))):
    m={}
    n,a,b,c,d=list(map(int,input().split()))
    print((f(n)))

# Optimized solution
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=min(k*d,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(eval(input()))):
    m={}
    n,a,b,c,d=list(map(int,input().split()))
    print((f(n)))
# Original solution
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=min(k*d,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(eval(input()))):
    m={}
    n,a,b,c,d=list(map(int,input().split()))
    print((f(n)))

# Optimized solution
from functools import lru_cache
for _ in range(int(eval(input()))):
    n,a,b,c,d=list(map(int,input().split()))
    @lru_cache(None)
    def f(k):
        if k==0:return 0
        if k==1:return d
        return min(k*d,f(k//5)+c+k%5*d,f(k//3)+b+k%3*d,f(k//2)+a+k%2*d,f((k+4)//5)+c+-k%5*d,f((k+2)//3)+b+-k%3*d,f((k+1)//2)+a+-k%2*d)
    print((f(n)))