You have an infinitely long digital panel. Using various combinations of 7 segments, we can represent each digit. The picture shows how all 10 decimal digits are displayed. 

Initially, all segments in the panel are off. You are given seven integers A, B, C, D, E, F and G representing the number of coins required to turn on the respective segment, as shown above.

Given an integer N, find the minimum number of coins you need to spend to display some [factor] of N on the panel.

------ Input Format ------ 

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The only line of each test case contains eight space-separated integers N, A, B, C, D, E, F and G, denoting the integer N and the number of coins required to turn on each of the seven segments.

------ Output Format ------ 

For each test case, output a single integer - the minimum number of coins you need to spend to display some factor of N on the panel.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N < 10^{100}$
$1 ≤ A, B, C, D, E, F, G ≤ 50$

----- Sample Input 1 ------ 
3
10 1 31 21 5 3 12 9
69697 1 2 3 4 5 6 7
3964083074239146524786 1 41 31 21 11 1 41

----- Sample Output 1 ------ 
48
5
72

----- explanation 1 ------ 
Test case $1$: $10$ has four factors: $1$, $2$, $5$, and $10$. Their costs are:
- Display $1$: $31+21=52$.
- Display $2$: $1+31+5+3+9=49$.
- Display $5$: $1+21+5+12+9=48$.
- Display $10$: $31+21+1+31+21+5+3+12=125$.

The minimum number of coins are required to display $5$, which costs $48$ coins.

Test case $2$: $69697$ has two factors: $1$ and $69697$. The cost to display $1$ is only $5$ coins, while the cost to display $69697$ is much larger, so the answer is $5$.

Difficulty: VERY_HARD
Tags: Complete search

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
from collections import deque
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	(n, l) = (l[0], l[1:])
	min_ = l[1] + l[2]
	c2 = sum(l) - l[2] - l[5]
	c5 = sum(l) - l[1] - l[4]
	c6 = sum(l) - l[1]
	q = deque()
	q.append((2, c2))
	q.append((5, c5))
	q.append((6, c6))
	while q:
		(num, cost) = q.popleft()
		if cost >= min_:
			continue
		if n % num == 0:
			min_ = min(min_, cost)
		q.append((num * 10 + 2, cost + c2))
		q.append((num * 10 + 5, cost + c5))
		q.append((num * 10 + 6, cost + c6))
	print(min_)


def dfs(a, b):
	if b >= 12:
		return
	__.append(int(a + '6'))
	dfs(a + '5', b + 1)
	dfs(a + '6', b + 1)

def check(cnt5, cnt6, n, p):
	test = 0
	if n % p != 0:
		return 2147483647
	while p != 0:
		if p % 10 == 5:
			test += cnt5
		elif p % 10 == 6:
			test += cnt6
		p //= 10
	return test
__ = []
dfs('', 0)
for _ in range(int(input())):
	Input = input().split()
	n = int(Input[0])
	(a, b, c, d, e, f, g) = map(int, [Input[1], Input[2], Input[3], Input[4], Input[5], Input[6], Input[7]])
	answer = b + c
	if n % 2 == 0:
		answer = min(answer, a + b + g + e + d)
	if n % 5 == 0:
		answer = min(answer, a + f + g + c + d)
	c5 = a + f + g + c + d
	c6 = a + f + g + c + d + e
	for p in __:
		answer = min(answer, check(c5, c6, n, p))
	print(answer)


t = int(input())
for tt in range(t):
	v = list(map(int, input().split()))
	n = v[0]
	v1 = v[2] + v[3]
	v6 = v[1] + v[3] + v[4] + v[5] + v[6] + v[7]
	v5 = v[1] + v[3] + v[4] + v[6] + v[7]
	v2 = v[1] + v[2] + v[4] + v[5] + v[7]
	ans = v1
	if n % 2 == 0:
		ans = min(ans, v2)
	if n % 5 == 0:
		ans = min(ans, v5)
	if n % 6 == 0:
		ans = min(ans, v6)
	for i in range(1, 2 ** 10):
		num = 0
		ic = i
		curc = 0
		while ic > 0:
			num *= 10
			if ic % 2 == 1:
				num += 6
				curc += v6
			else:
				num += 5
				curc += v5
			ic = ic // 2
		if n % num == 0:
			ans = min(ans, curc)
	print(ans)


def helper(cnt5, cnt6, n, p):
	hh = 0
	if n % p != 0:
		return 2147483647
	while p != 0:
		if p % 10 == 5:
			hh += cnt5
		elif p % 10 == 6:
			hh += cnt6
		p //= 10
	return hh
__ = []

def trave(a, b):
	if b >= 12:
		return
	__.append(int(a + '6'))
	trave(a + '5', b + 1)
	trave(a + '6', b + 1)
trave('', 0)
for _ in range(int(input())):
	Input = input().split()
	n = int(Input[0])
	(a, b, c, d, e, f, g) = map(int, [Input[1], Input[2], Input[3], Input[4], Input[5], Input[6], Input[7]])
	res = b + c
	if n % 2 == 0:
		res = min(res, a + b + g + e + d)
	if n % 5 == 0:
		res = min(res, a + f + g + c + d)
	g1 = a + f + g + c + d
	jj = a + f + g + c + d + e
	for p in __:
		res = min(res, helper(g1, jj, n, p))
	print(res)


import io, os, time, sys
t = int(input())

def solve(num, digits, cost, cost_2, cost_6, cost_5, number):
	global ans
	if digits == 0:
		if ans > cost and number % num == 0:
			ans = cost
		return
	if ans > cost and number % num == 0:
		ans = cost
		return
	num = num * 10 + 2
	cost += cost_2
	solve(num, digits - 1, cost, cost_2, cost_6, cost_5, number)
	num = num // 10
	num = num * 10 + 5
	cost -= cost_2
	cost += cost_5
	solve(num, digits - 1, cost, cost_2, cost_6, cost_5, number)
	num = num // 10
	num = num * 10 + 6
	cost -= cost_5
	cost += cost_6
	solve(num, digits - 1, cost, cost_2, cost_6, cost_5, number)
for i in range(t):
	sample_input = list(map(int, input().split()))
	global ans
	num = sample_input[0]
	ans = sample_input[2] + sample_input[3]
	cost_2 = sample_input[1] + sample_input[2] + sample_input[4] + sample_input[5] + sample_input[7]
	cost_5 = sample_input[1] + sample_input[6] + sample_input[7] + sample_input[3] + sample_input[4]
	cost_6 = sample_input[1] + sample_input[6] + sample_input[7] + sample_input[3] + sample_input[4] + sample_input[5]
	solve(2, 8, cost_2, cost_2, cost_6, cost_5, num)
	solve(5, 8, cost_5, cost_2, cost_6, cost_5, num)
	solve(6, 8, cost_6, cost_2, cost_6, cost_5, num)
	sys.stdout.write(str(ans) + '\n')


def depthperbreadth(armstring, bruce):
	if bruce >= 12:
		return
	__.append(int(armstring + '6'))
	depthperbreadth(armstring + '5', bruce + 1)
	depthperbreadth(armstring + '6', bruce + 1)

def checkmate(cnt5, cnt6, nicolas, princes):
	testcases = 0
	if nicolas % princes != 0:
		return 2147483647
	while princes != 0:
		if princes % 10 == 5:
			testcases += cnt5
		elif princes % 10 == 6:
			testcases += cnt6
		princes //= 10
	return testcases
__ = []
depthperbreadth('', 0)
for _ in range(int(input())):
	idontknowthisvar = input().split()
	nicolas = int(idontknowthisvar[0])
	(armstring, bruce, c, d, e, f, g) = map(int, [idontknowthisvar[1], idontknowthisvar[2], idontknowthisvar[3], idontknowthisvar[4], idontknowthisvar[5], idontknowthisvar[6], idontknowthisvar[7]])
	answer = bruce + c
	if nicolas % 2 == 0:
		answer = min(answer, armstring + bruce + g + e + d)
	if nicolas % 5 == 0:
		answer = min(answer, armstring + f + g + c + d)
	c5 = armstring + f + g + c + d
	c6 = armstring + f + g + c + d + e
	for princes in __:
		answer = min(answer, checkmate(c5, c6, nicolas, princes))
	print(answer)


from math import gcd

def dfs(a, b):
	gcd(3, 8)
	if b >= 12 and True:
		gcd(3, 8)
		return
	__.append(int(a + '6'))
	gcd(3, 8)
	dfs(a + '5', b + 1)
	gcd(3, 8)
	dfs(a + '6', b + 1)
	gcd(3, 8)

def check(cnt5, cnt6, n, p):
	test = 0
	gcd(3, 8)
	if n % p != 0 and True:
		gcd(3, 8)
		return 2147483647
	while p != 0 and True:
		gcd(3, 8)
		if p % 10 == 5:
			gcd(3, 8)
			test += cnt5
			gcd(3, 8)
		else:
			gcd(3, 8)
			if p % 10 == 6 and True:
				gcd(3, 8)
				test += cnt6
				gcd(3, 8)
		p //= 10
		gcd(3, 8)
	return test
__ = []
gcd(3, 8)
dfs('', 0)
gcd(3, 8)
for _ in range(int(input())):
	gcd(3, 8)
	Input = input().split()
	n = int(Input[0])
	gcd(3, 8)
	(a, b, c, d, e, f, g) = map(int, [Input[1], Input[2], Input[3], Input[4], Input[5], Input[6], Input[7]])
	answer = b + c
	gcd(3, 8)
	if n % 2 == 0 and True:
		gcd(3, 8)
		answer = min(answer, a + b + g + e + d)
	if n % 5 == 0 and True:
		gcd(3, 8)
		answer = min(answer, a + f + g + c + d)
		gcd(3, 8)
	c5 = a + f + g + c + d
	gcd(3, 8)
	c6 = a + f + g + c + d + e
	gcd(3, 8)
	for p in __:
		gcd(3, 8)
		gcd(4, 9)
		answer = min(answer, check(c5, c6, n, p))
		gcd(3, 8)
		gcd(4, 9)
	print(answer)
	gcd(3, 8)


def getSum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum

def solve(n, cur, num, power, ans, five, six):
	if cur > ans:
		return 100000000
	if n % num == 0:
		return cur
	return min(solve(n, cur + five, 5 * power + num, power * 10, ans, five, six), solve(n, cur + six, 6 * power + num, 10 * power, ans, five, six))
t = int(input())
while t > 0:
	a = list(map(int, input().split()))
	n = a[0]
	a = a[1:]
	two = a[0] + a[1] + a[3] + a[4] + a[6]
	five = a[0] + a[5] + a[3] + a[2] + a[6]
	six = a[0] + a[5] + a[3] + a[2] + a[6] + a[4]
	ans = a[1] + a[2]
	if n % 2 == 0:
		ans = min(ans, two)
		if getSum(n) % 3 == 0:
			ans = min(ans, six)
	if n % 5 == 0:
		ans = min(ans, five)
	cur = six
	num = 6
	power = 10
	ans = min(solve(n, cur, num, power, ans, five, six), ans)
	print(ans)
	t -= 1