题目背景

翻译自 NERC 2018 G 题。

题目描述

你作为某知名大学的客座学生，你想要在那里学习 $k$ 节课，但同时很遗憾，对于每周，你只有特定的时间才能有空去听课，如果 $a_i = 1$，说明周 $i$ 你有空，反之则没空。

你需要安排一个合理的日程，使得你去听第一节课到最后一节课中间经过的时间最短，当然第一节课听什么的顺序由你决定。

输入格式

第一行一个整数 $t (1 \leq t \leq 10000)$，表示数据组数。

接下来每组数据第一行一个整数 $k (1 \leq k \leq 10^8)$。

然后 $7$ 个整数 $a_1 \sim a_7$，$a_i = 1$ 表示有空，$a_i = 0$ 表示没空。

输出格式

对于每组数据，输出一个整数，表示最短的从第一节课到最后一节课所经过的时间。

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

提示

对于所有数据，保证 $1 \leq t \leq 10000$，$1 \leq k \leq 10^8$ 且 $a_i \in \{0,1\}$。

对于样例一，从周二开始听课听到下周二，经过 $8$ 天。