Berland State University invites people from all over the world as guest students. You can come to the capital of Berland and study with the best teachers in the country.

Berland State University works every day of the week, but classes for guest students are held on the following schedule. You know the sequence of seven integers $a_1, a_2, \dots, a_7$ ($a_i = 0$ or $a_i = 1$):  $a_1=1$ if and only if there are classes for guest students on Sundays;  $a_2=1$ if and only if there are classes for guest students on Mondays;  ...   $a_7=1$ if and only if there are classes for guest students on Saturdays. 

The classes for guest students are held in at least one day of a week.

You want to visit the capital of Berland and spend the minimum number of days in it to study $k$ days as a guest student in Berland State University. Write a program to find the length of the shortest continuous period of days to stay in the capital to study exactly $k$ days as a guest student.


-----Input-----

The first line of the input contains integer $t$ ($1 \le t \le 10\,000$) — the number of test cases to process. For each test case independently solve the problem and print the answer. 

Each test case consists of two lines. The first of them contains integer $k$ ($1 \le k \le 10^8$) — the required number of days to study as a guest student. The second line contains exactly seven integers $a_1, a_2, \dots, a_7$ ($a_i = 0$ or $a_i = 1$) where $a_i=1$ if and only if classes for guest students are held on the $i$-th day of a week.


-----Output-----

Print $t$ lines, the $i$-th line should contain the answer for the $i$-th test case — the length of the shortest continuous period of days you need to stay to study exactly $k$ days as a guest student.


-----Example-----
Input
3
2
0 1 0 0 0 0 0
100000000
1 0 0 0 1 0 1
1
1 0 0 0 0 0 0

Output
8
233333332
1



-----Note-----

In the first test case you must arrive to the capital of Berland on Monday, have classes on this day, spend a week until next Monday and have classes on the next Monday. In total you need to spend $8$ days in the capital of Berland.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
def solve(k, a):
	w = sum(a)
	ans = float('inf')
	if k <= w:
		for start in range(7):
			for end in range(start, 8):
				if sum(a[start:end]) >= k:
					ans = min(ans, end - start)
	for start in range(7):
		for end in range(7):
			x = sum(a[start:])
			y = sum(a[:end + 1])
			z = k - x - y
			if z >= 0 and z % w == 0:
				ans = min(ans, z // w * 7 + end + 1 + 7 - start)
	return ans
T = int(input())
ans = []
for ti in range(T):
	K = int(input())
	A = [int(x) for x in input().split()]
	ans.append(solve(K, A))
print('\n'.join(map(str, ans)))


_ = int(input())
for __ in [0] * _:
	day = int(input())
	sche = [int(i) for i in input().split()]
	week = sum(sche)
	left = day % week + week
	total = day // week * 7 - 7
	last = sche.index(1)
	s = []
	for i in range(sche.index(1) + 1, 7):
		if sche[i]:
			s.append(i - last - 1)
			last = i
	s.append(7 - sum(s) - len(s) - 1)
	l = len(s)
	total += left
	time = 14
	interval = s + s[:]
	for i in range(l + 1):
		time = min(time, sum(interval[:left - 1]))
		interval.append(interval.pop(0))
	print(total + time)


def f(target):
	(i, j) = (0, 0)
	n = 14
	l = n
	c = 0
	while j < n:
		if a[j]:
			c += 1
		while c > target or a[i] == 0:
			if a[i]:
				c -= 1
			i += 1
			if i == j:
				break
		if c == target:
			l = min(l, j - i + 1)
		j += 1
	return l
for _ in range(int(input())):
	k = int(input())
	a = [int(i) for i in input().split()]
	t = sum(a)
	ans = k // t * 7
	rem = k % t
	a *= 2
	if rem == 0:
		print(ans - 7 + f(t))
	else:
		print(ans + f(rem))


t = int(input())
for i in range(t):
	k = int(input())
	a = list(map(int, input().split()))
	sm = sum(a)
	ans = 0
	if k % sm == 0:
		ans = (k // sm - 1) * 7
		k = sm
	else:
		ans = k // sm * 7
		k %= sm
	ad = 7
	for i in range(7):
		day = 0
		cnt = k
		for j in range(i, i + 7):
			j %= 7
			day += 1
			cnt -= a[j]
			if cnt == 0:
				ad = min(ad, day)
				break
	print(ans + ad)


for _ in range(int(input())):
	k = int(input())
	days = list(map(int, input().strip().split()))
	sd = sum(days)
	ans = 0
	if k > sd:
		t = k // sd
		ans += t * 7
		k = k % sd
	if k == 0:
		k += sd
		ans -= 7
	ways = [days[start:] + days[:start] for start in range(7)]
	minw = 7
	for way in ways:
		sk = k
		d = 0
		for v in way:
			sk -= v
			d += 1
			if sk == 0:
				break
		if minw > d:
			minw = d
	ans += minw
	print(ans)


for _ in range(int(input())):
	k = int(input())
	a = [int(x) for x in input().split()]
	m = sum(a)
	y = k % m
	if y == 0:
		y = m
	x = (k - y) // m
	a1 = a + a
	ml = 100
	for i in range(14):
		s = 0
		for j in range(i, 14):
			s += a1[j]
			if s == y:
				ml = min(ml, j - i + 1)
	ans = 7 * x + ml
	print(ans)


t = int(input())
for u in range(t):
	k = int(input())
	a = list(map(int, input().split()))
	per = a.count(1)
	breaks = []
	b = a + a
	curr = 1
	ind = b.index(1) + 1
	for i in range(7):
		if b[ind] == 0:
			curr += 1
			ind += 1
		else:
			breaks.append(curr)
			curr = 1
			ind += 1
	z = k % per
	if z == 0:
		print(7 * (k // per) - max(breaks) + 1)
	elif z == 1:
		print(7 * (k // per) + 1)
	else:
		brea = breaks + breaks
		sums = [sum(brea[:z - 1])]
		for i in range(per - 1):
			sums.append(sums[-1] + brea[z + i - 1] - brea[i])
		print(7 * (k // per) + 1 + min(sums))


from sys import stdin
for _ in range(int(stdin.readline())):
	K = int(stdin.readline())
	lst = [*map(int, stdin.readline().split())]
	(ans, item) = ([], 0)
	for (i, x) in enumerate(lst):
		if x == 1:
			ans.append(i)
			item += 1
	res = 100000000000000000000000
	for (i, x) in enumerate(ans):
		k = K
		elem = 0
		if k <= item - i:
			elem = ans[i + k - 1] - x + 1
		else:
			elem += 7 - x
			k -= item - i
			elem += k // item * 7
			k = k % item
			if k == 0:
				elem -= 7 - ans[-1] - 1
			else:
				elem += ans[k - 1] + 1
		res = min(res, elem)
	print(res)


from sys import stdin, stdout
t = int(stdin.readline().strip())

def solve(k, days):
	x = sum(days)
	three_week_period = []
	for i in range(4):
		for j in days:
			three_week_period.append(j)
	working_days = {}
	for i in range(0, 21):
		for j in range(0, 28 - i):
			t_working_days = sum(three_week_period[j:j + i])
			if t_working_days in working_days:
				if i < working_days[t_working_days]:
					working_days[t_working_days] = i
			else:
				working_days[t_working_days] = i
	if k >= 3 * x:
		t1 = k // x
		complete_weeks = t1 - 2
		remaining_working_days = k - complete_weeks * x
		return complete_weeks * 7 + working_days[remaining_working_days]
	else:
		return working_days[k]
for _ in range(t):
	k = int(stdin.readline().strip())
	days = list(map(int, stdin.readline().strip().split(' ')))
	stdout.write(str(solve(k, days)) + '\n')


import os, sys
from io import BytesIO, IOBase

def solve(k1, a):
	x = a.count(1)
	d = 10 ** 10
	for i in range(7):
		(d1, k, fl) = (0, k1, 0)
		for j in range(i, 7):
			k -= a[j] == 1
			d1 += 1
			if not k:
				d = min(d1, d)
				fl = 1
				break
		if not fl:
			d1 += 7 * (k // x - (k % x == 0))
			k = k % x if k % x else x
			for j in range(7):
				k -= a[j] == 1
				d1 += 1
				if not k:
					d = min(d, d1)
					break
	return d

def main():
	for _ in range(int(input())):
		k = int(input())
		a = list(map(int, input().split()))
		print(solve(k, a))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	count = int(input())
	for x in range(count):
		lessons = int(input())
		arr = input().split()
		tot = 0
		for y in arr:
			if y == '1':
				tot += 1
		if lessons % tot == 0:
			a = lessons // tot - 1
			b = tot
		else:
			a = lessons // tot
			b = lessons % tot
		store = 7
		for y in range(7):
			test = 0
			for z in range(7):
				if arr[(y + z) % 7] == '1':
					test += 1
				if test == b:
					break
			store = min(store, z + 1)
		print(a * 7 + store)
main()


for _ in range(int(input())):
	k = int(input())
	a = tuple(map(int, input().split()))
	cnt = sum(a)
	(weeks, k) = divmod(k - 1, cnt)
	ans = 1 << 32
	for i in range(7):
		x = 0
		for j in range(7):
			x += a[(i + j) % 7]
			if x == k + 1:
				ans = min(ans, j + 1)
				break
	print(7 * weeks + ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	orga = list(map(int, input().split()))
	mini = pow(10, 8) * 7 + 1
	for i in range(7):
		a = orga[i:] + orga[0:i]
		one = a.count(1)
		weeks = n // one
		days = weeks * 7
		rem = n % one
		if rem == 0:
			days -= 7
			rem = one
		extday = 0
		for i in a:
			if rem == 0:
				break
			extday += 1
			if i == 1:
				rem -= 1
		mini = min(mini, days + extday)
	print(mini)


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())
t = nu()
for it in range(t):
	k = nu()
	a = li()
	s = sum(a)
	zz = []
	for i in range(7):
		pp = 0
		cc = k
		for j in range(i, 7):
			pp += 1
			cc -= a[j]
			if cc == 0:
				break
		if cc == 0:
			zz.append(pp)
			continue
		kl = cc % s
		if kl == 0:
			nm = cc // s - 1
		else:
			nm = cc // s
		cc = cc - nm * s
		nm = nm * 7
		pp += nm
		for j in range(0, 7):
			if cc == 0:
				break
			pp += 1
			cc -= a[j]
		zz.append(pp)
	print(min(zz))


def solve():
	k = int(input())
	w = tuple(map(int, input().split()))
	cnt = sum(w)
	(weeks, k) = divmod(k - 1, cnt)
	d = 1 << 32
	for i in range(7):
		c = 0
		for j in range(7):
			c += w[(i + j) % 7]
			if c == k + 1:
				d = min(d, j + 1)
				break
	print(7 * weeks + d)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = a.count(1)
	p = n // s
	q = n % s
	if q == 0:
		w = s
	else:
		w = q
	num = float('inf')
	for j in range(7):
		tmp = 0
		cnt = 0
		for k in range(7):
			tmp += a[(j + k) % 7]
			cnt += 1
			if tmp == w:
				num = min(num, cnt)
				break
	if n - s <= 0:
		print(num)
	elif q == 0:
		print(7 * (p - 1) + num)
	else:
		print(7 * p + num)


N = int(input())
for i in range(N):
	k = int(input())
	a = [int(u) for u in input().split()]
	cc = sum(a)
	if cc == 1:
		ans = (k - 1) * 7 + 1
	else:
		if k % cc == 0:
			ans = (k - cc) // cc * 7
			left = cc
		else:
			ans = k // cc * 7
			left = k % cc
		mini = 10000
		for i in range(7):
			cur = 0
			go = left
			for j in range(7):
				if go == 0:
					break
				cur += 1
				if a[(i + j) % 7] == 1:
					go -= 1
			if cur < mini:
				mini = cur
		ans += mini
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(1)
	if c >= n:
		p = 7
		for j in range(7):
			s = 0
			for k in range(j, 7):
				s = s + a[k]
				if s == n:
					p = min(p, k - j + 1)
			if s < n:
				for m in range(j):
					s = s + a[m]
					if s == n:
						p = min(p, 7 - j + m + 1)
			else:
				continue
		print(p)
	else:
		p = n // c
		if n % c != 0:
			c = n % c
			an = p * 7
		else:
			an = (p - 1) * 7
		p = 7
		for j in range(7):
			s = 0
			for k in range(j, 7):
				s = s + a[k]
				if s == c:
					p = min(p, k - j + 1)
			if s < c:
				for m in range(j):
					s = s + a[m]
					if s == c:
						p = min(p, 7 - j + m + 1)
			else:
				continue
		print(an + p)


from math import sqrt

def phi(u):
	ans = u
	for i in range(2, int(sqrt(n)) + 1):
		if u % i == 0:
			while u % i == 0:
				u = u / i
			ans = ans - int(ans / i)
	if n > 1:
		ans = ans - int(ans / n)
	return ans

def binpow(u, a, mod):
	ans = 1
	if a == 0:
		return 1
	while a > 0:
		if a % 2 == 0:
			u = u ** 2 % mod
			a = int(a / 2)
		else:
			ans = ans * u % mod
			a = a - 1
	return int(ans)

def ffind(s, u):
	if u == 0:
		return -1
	ans = -1
	while u > 0:
		ans = s.find('1', ans + 1)
		u = u - 1
	return ans
n = int(input())
while n > 0:
	k = int(input())
	ss = input().split(' ')
	s = ''
	for i in ss:
		s = s + i
	mx = 1000000000
	u = s.count('1')
	for i in range(7):
		d = s[i:].count('1')
		ans = 0
		if d >= k:
			ans = ffind(s[i:], k) + 1
		else:
			dd = int((k - d) / u)
			ans = 7 - i + 7 * dd + ffind(s, k - d - dd * u) + 1
			if k == d + dd * u:
				ans = ans - s[-1::-1].find('1')
		mx = min(mx, ans)
	print(mx)
	n = n - 1


t = int(input())
while t:
	k = int(input())
	a = [int(i) for i in input().split()]
	da = [999] * 8
	cnt = sum(a)
	for i in range(0, 7):
		if not a[i]:
			continue
		tmp_cnt = 0
		for j in range(0, 7):
			x = (i + j) % 7
			if not a[x]:
				continue
			tmp_cnt += 1
			da[tmp_cnt] = min(da[tmp_cnt], j + 1)
	if k % cnt:
		print(k // cnt * 7 + da[k % cnt])
	else:
		print(k // cnt * 7 - 7 + da[cnt])
	t -= 1


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = n
	e = sum(l)
	fa = 9999999999999999999999
	if m <= e:
		for j in range(7):
			m = n
			for k in range(7):
				m -= l[(j + k) % 7]
				if m == 0:
					fa = min(fa, k + 1)
					break
	else:
		for j in range(7):
			m = n
			ans = 0
			m -= sum(l[j:])
			ans = 7 - j
			if m > e:
				ans += m // e * 7
				m -= m // e * e
			t = 0
			if m == 0:
				ind = l[::-1].index(1)
				ans -= ind
			while m > 0:
				ans += 1
				m -= l[t]
				t += 1
			fa = min(ans, fa)
	print(fa)


import sys

def rl(proc=None):
	if proc is not None:
		return proc(sys.stdin.readline())
	else:
		return sys.stdin.readline().rstrip()

def srl(proc=None):
	if proc is not None:
		return list(map(proc, rl().split()))
	else:
		return rl().split()

def test(K, A, i):
	r = 0
	while K > 0:
		if A[(r + i) % 7]:
			K -= 1
		r += 1
	return r

def brute(K, A):
	best = 1 << 60
	for i in range(7):
		if A[i]:
			best = min(best, test(K, A, i))
	return best

def solve(K, A):
	s = sum(A)
	if s == 0:
		return -1
	if K < 32:
		return brute(K, A)
	full_weeks = (K - 2 * s) // s
	K -= full_weeks * s
	return 7 * full_weeks + brute(K, A)

def main():
	T = rl(int)
	for t in range(1, T + 1):
		K = rl(int)
		A = srl(int)
		print(solve(K, A))
main()


import sys
import math
import bisect

def solve(A, first, m):
	ans = 0
	week_val = sum(A)
	for i in range(first, 7):
		m -= A[i]
		ans += 1
		if m == 0:
			break
	if m > week_val:
		if m % week_val == 0:
			ans += 7 * (m // week_val - 1)
			m = week_val
		else:
			ans += 7 * (m // week_val)
			m %= week_val
	if m:
		for i in range(7):
			m -= A[i]
			ans += 1
			if m == 0:
				break
	return ans

def main():
	for _ in range(int(input())):
		m = int(input())
		A = list(map(int, input().split()))
		min_val = 10 ** 18
		for i in range(7):
			val = solve(A, i, m)
			min_val = min(min_val, val)
		print(min_val)

def __starting_point():
	main()
__starting_point()


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(iinp()):
	n = iinp()
	arr = lmp()
	c = arr.count(1)
	ml = l1d(c, inf)
	for i in range(7):
		if arr[i]:
			x = 0
			for j in range(i, i + 7):
				if arr[j % 7]:
					ml[x] = min(ml[x], j - i + 1)
					x += 1
	print((n - 1) // c * 7 + ml[(n - 1) % c])


t = int(input())
for i in range(t):
	k = int(input())
	a = list(map(int, input().split()))
	wd = sum(a)
	rem = k % wd
	q = k // wd
	if rem == 0:
		rem = wd
		q = max(0, q - 1)
	ma = 10
	for i in range(7):
		ls = 0
		for j in range(i, i + 7):
			ls += a[j % 7]
			if ls >= rem:
				ma = min(ma, j - i + 1)
				break
	print(q * 7 + ma)


t = int(input())
for i in range(t):
	k = int(input())
	week = [int(x) for x in input().split()]
	i = 1
	need = {}
	happy = sun = 0
	answer = 10 ** 100
	for item in week:
		if item == 1:
			happy += 1
			need[happy] = i
		i += 1
	week.reverse()
	for item in week:
		if item == 0:
			sun += 1
		else:
			break
	week.reverse()
	need[0] = 0
	i = happy
	for item in week:
		if item == 1:
			counter = 8 - need[happy - i + 1] + (k - i) // happy * 7 + need[(k - i) % happy]
			if (k - i) % happy == 0:
				counter -= sun
			answer = min(answer, counter)
			i -= 1
	print(answer)


from collections import *
import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(rint()):
		(n, a) = (rint(), deque(rints()))
		(su, ans) = (sum(a), float('inf'))
		(days, mod) = divmod(n, su)
		if mod == 0:
			days -= 1
			mod = su
		for i in range(7):
			tem = 0
			for (j, k) in enumerate(a, 1):
				if k == 1:
					tem += 1
					if tem == mod:
						ans = min(ans, days * 7 + j)
						break
			a.rotate(-1)
		print(ans)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()


from math import ceil

def main():
	k = int(input())
	d = [idx for (idx, di) in enumerate(input().split()) if di == '1']
	dow = len(d)
	w = ceil(k / dow) - 1
	m = k % dow
	ans = [d[(m - 1 + x) % dow] + 7 * (w + int(m - 1 + x >= (dow if m else 0))) - d[x] + 1 for x in range(dow)]
	print(min(ans))
for _ in range(int(input())):
	main()


import sys
n = int(sys.stdin.readline())
for i in range(n):
	lessons = int(sys.stdin.readline())
	tmpSchedule = str(sys.stdin.readline()).split()
	ans = -1
	for j in range(7):
		schedule = [tmpSchedule[k % 7] for k in range(j, j + 7)]
		worked = []
		for i in range(len(schedule)):
			if schedule[i] == '1':
				worked.append(i + 1)
		atWeek = schedule.count('1')
		tmpAns = (lessons - 1) // atWeek * 7
		tmp = lessons % atWeek - 1
		if tmp < 0:
			tmp = len(worked) - 1
		tmpAns += worked[tmp] - worked[0] + 1
		if tmpAns < ans or ans == -1:
			ans = tmpAns
	print(ans)


import math
from collections import defaultdict
ml = lambda : map(int, input().split())
ll = lambda : list(map(int, input().split()))
ii = lambda : int(input())
ip = lambda : input()
t = ii()
for _ in range(t):
	n = ii()
	a = ll()
	b = a.count(1)
	if n % b == 0:
		ans = (n // b - 1) * 7
		c = b
	else:
		ans = n // b * 7
		c = n % b
	temp = 0
	if c > 0:
		temp = 1000000000
		for i in range(7):
			if a[i] == 1:
				k = 0
				for j in range(7):
					if a[(i + j) % 7] == 1:
						k += 1
					if k == c:
						break
				if k == c:
					temp = min(temp, j + 1)
	print(temp + ans)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(ri()):
		k = ri()
		a = ria()
		n1 = a.count(1)
		currdays = 7 * max(0, int(k / n1) - 1)
		kleft = k - max(0, n1 * (int(k / n1) - 1))
		da = 3 * a
		mi1 = 100
		mi2 = 100
		for i in range(7):
			c = 0
			if a[i] == 1:
				for j in range(i, 21):
					if da[j] == 1:
						c += 1
						if c == kleft:
							if currdays == 0:
								mi1 = min(mi1, j - i + 1)
							else:
								mi2 = min(mi2, max(0, j - i + 1))
		print(min(mi1, mi2) + currdays)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()