Background

Translated from Problem G of NERC 2018.

Problem Description

As a guest student at a well-known university, you want to attend $k$ classes. Unfortunately, in each week you are only available at certain times to attend classes. If $a_i = 1$, it means you are available in week $i$; otherwise you are not.

You need to arrange a schedule so that the time from attending the first class to attending the last class is as short as possible. Of course, you can decide on which available time you attend the first class.

Input Format

The first line contains an integer $t \ (1 \leq t \leq 10000)$, the number of test cases.

For each test case, the first line contains an integer $k \ (1 \leq k \leq 10^8)$.

Then follow $7$ integers $a_1 \sim a_7$, where $a_i = 1$ means available and $a_i = 0$ means not available.

Output Format

For each test case, output one integer, the minimum time from the first class to the last class.

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

8
233333332
1

Hint

For all testdata, it is guaranteed that $1 \leq t \leq 10000$, $1 \leq k \leq 10^8$, and $a_i \in \{0,1\}$.

For sample 1, if you start attending classes from Tuesday and attend until next Tuesday, $8$ days pass.

Translated by ChatGPT 5