Buggy python submission (verdict: Time Limit Exceeded):
costs = {}
searching = {}

def init(a, b, c, d):
    my_costs = {}
    my_costs[0] = 0
    frontier = set([0])
    for depth in range(8):
        new_frontier = set()
        for f in frontier:
            for ff, cst in [(f*2, a), (f*3, b), (f*5, c), (f-1, d), (f+1, d)]:
                if ff < 0:
                    continue
                if ff not in my_costs:
                    my_costs[ff] = my_costs[f] + cst
                else:
                    my_costs[ff] = min(my_costs[f] + cst, my_costs[ff])
                new_frontier.add(ff)
        frontier = new_frontier
    for k in range(20):
        costs[k] = my_costs[k]

def solve(n, a, b, c, d):
    if n in costs:
        return costs[n]

    next_step = {}
    for delta in range(-5, 5+1):
        m = n + delta
        for div, div_cost in [(2, a), (3, b), (5, c)]:
            if m % div == 0:
                cst = d * abs(delta) + div_cost
                r = m // div
                if r not in next_step:
                    next_step[r] = cst
                else:
                    next_step[r] = min(next_step[r], cst)

    #print(f'next step for {n} is {list(next_step.keys())}')
    costs_lst = []
    for r in next_step:
        cst = solve(r, a, b, c, d) + next_step[r]
        costs_lst.append(cst)
    costs[n] = min(costs_lst + [n*d])
    return costs[n]

t = int(input())

for casenum in range(1, t+1):
    n, a, b, c, d = map(int, input().split())
    costs = {}
    searching = {}

    init(a, b, c, d)
    answer = solve(n, a, b, c, d)
    #print(f'answer for {n, a, b, c, d} = {answer}')
    print(answer)

Fixed submission:
costs = {}
searching = {}

def init(a, b, c, d):
    my_costs = {}
    my_costs[0] = 0
    frontier = set([0])
    for depth in range(8):
        new_frontier = set()
        for f in frontier:
            for ff, cst in [(f*2, a), (f*3, b), (f*5, c), (f-1, d), (f+1, d)]:
                if ff < 0:
                    continue
                if ff not in my_costs:
                    my_costs[ff] = my_costs[f] + cst
                else:
                    my_costs[ff] = min(my_costs[f] + cst, my_costs[ff])
                new_frontier.add(ff)
        frontier = new_frontier
    for k in range(20):
        costs[k] = my_costs[k]

def solve(n, a, b, c, d):
    if n in costs:
        return costs[n]

    next_step = {}
    for delta in range(-5, 5+1):
        m = n + delta
        for div, div_cost in [(2, a), (3, b), (5, c)]:
            if m % div == 0:
                cst = d * abs(delta) + div_cost
                r = m // div
                if r not in next_step:
                    next_step[r] = cst
                else:
                    next_step[r] = min(next_step[r], cst)

    #print(f'next step for {n} is {list(next_step.keys())}')
    costs_lst = []
    for r in next_step:
        cst = solve(r, a, b, c, d) + next_step[r]
        costs_lst.append(cst)
    costs[n] = min(costs_lst + [n*d])
    return costs[n]

t = int(input())

for casenum in range(1, t+1):
    n, a, b, c, d = map(int, input().split())
    costs = {}
    searching = {}

    init(a, b, c, d)
    answer = solve(n, a, b, c, d)
    #print(f'answer for {n, a, b, c, d} = {answer}')
    print(answer)