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: interview

Starter code:

Solutions:
import math as ma
import sys
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))

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)


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()))
    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)

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()


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 12/3/18

"""




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)))


3
# -*- coding: utf-8 -*-

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))

def __starting_point():
    main()

__starting_point()

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


#In the name of GOD!
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)


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()


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)
    else:
        if q == 0:
            print(7 * (p - 1) + num)
        else:
            print(7 * p + num)


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))

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)


_=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=[]#intervals
    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)
        
    


for i in range (int(input())) :
    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, cnt = 0, 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())
    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())
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)
            
            


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)]
    #l = schedule.find('1')
    #r = schedule.rfind('1')
        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)


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

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))
    # print(ans)

for _ in range(int(input())): main()

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)

import sys
import math
import bisect

def solve(A, first, m):
    ans = 0
    week_val = sum(A)
    #print('first: %d' % first)
    for i in range(first, 7):
        m -= A[i]
        ans += 1
        if m == 0:
            break
    #print('after the first week, m: %d, ans: %d' % (m, ans))
    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
    #print('after middle weeks, m: %d, ans: %d' % (m, ans))
    if m:
        for i in range(7):
            m -= A[i]
            ans += 1
            if m == 0:
                break
    #print('after the last week, m: %d, ans: %d' % (m, ans))
    return ans

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

def __starting_point():
    main()

__starting_point()

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)