Berland 国立大学邀请来自世界各地的人们作为访问学生。你可以来到 Berland 的首都，与全国最优秀的教师一起学习。

Berland 国立大学在一周中的每一天都开放，但针对访问学生的课程安排如下。已知一个包含七个整数的序列 $a_1, a_2, \dots, a_7$（其中 $a_i = 0$ 或 $a_i = 1$）：

• $a_1 = 1$ 当且仅当周日有针对访问学生的课程；
• $a_2 = 1$ 当且仅当周一有针对访问学生的课程；
• $\dots$
• $a_7 = 1$ 当且仅当周六有针对访问学生的课程。

针对访问学生的课程每周至少有一天。

你想要访问 Berland 的首都，并希望通过在首都停留最少天数来完成 $k$ 天的访问学生课程学习。请编写一个程序，计算为了学习恰好 $k$ 天课程所需的最短连续停留天数。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示需要处理的测试用例数量。每个测试用例独立求解并输出答案。

每个测试用例包含两行。第一行包含一个整数 $k$ ($1 \le k \le 10^8$)，表示需要学习的课程天数。第二行包含七个整数 $a_1, a_2, \dots, a_7$ ($a_i = 0$ 或 $a_i = 1$)，其中 $a_i = 1$ 当且仅当一周中的第 $i$ 天有针对访问学生的课程。

输出格式

输出 $t$ 行，第 $i$ 行应包含第 $i$ 个测试用例的答案，即为了学习恰好 $k$ 天课程所需的最短连续停留天数。

样例

输入 1

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

输出 1

8
233333332
1

说明

在第一个测试用例中，你必须在周一到达 Berland 首都，当天参加课程，度过一周直到下周一，并在下周一再次参加课程。总共需要在 Berland 首都停留 8 天。