mod = 1000000007
eps = 10 ** -9
inf = 10 ** 40


def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline

    for t in range(int(input())):
        N, a, b, c, d = map(int, input().split())
        que = []

        heappush(que, -N)
        seen = {N: 0}
        while que:
            n = -heappop(que)
            if n == 1:
                seen[0] = seen[1] + d
                break
            # 2
            n2_minor = n // 2
            if n % 2 == 0:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d)
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d))
            else:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d) + d
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d) + d)
                n2_major = n2_minor + 1
                if n2_major not in seen:
                    seen[n2_major] = seen[n] + min(a, n2_major * d) + d
                    heappush(que, -n2_major)
                else:
                    seen[n2_major] = min(seen[n2_major], seen[n] + min(a, n2_major * d) + d)

            # 3
            n3_minor = n // 3
            if n % 3 == 0:
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d)
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d))
            else:
                mod3 = n % 3
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d) + d * mod3
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d) + d * mod3)
                n3_major = n3_minor + 1
                if n3_major not in seen:
                    seen[n3_major] = seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3)
                    heappush(que, -n3_major)
                else:
                    seen[n3_major] = min(seen[n3_major], seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3))

            # 5
            n5_minor = n // 5
            if n % 5 == 0:
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4)
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4))
            else:
                mod5 = n % 5
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4) + d * mod5
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4) + d * mod5)
                n5_major = n5_minor + 1
                if n5_major not in seen:
                    seen[n5_major] = seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5)
                    heappush(que, -n5_major)
                else:
                    seen[n5_major] = min(seen[n5_major], seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5))
        print(seen[0])
        # if t == 0:
        #    print(seen)


if __name__ == '__main__':
    main()


Measured memory_bytes: 105660