human
Can you provide a Python 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 given the following:
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, ..., 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 ≤ t ≤ 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 ≤ k ≤ 10^8) — the required number of days to study as a guest student. The second line contains exactly seven integers a_1, a_2, ..., 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.
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python 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.

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

# region fastio
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,...