← 返回题目列表

Codeforces · 1089/G

G. 客座学生

中文机器翻译题面 查看原题

伯兰州立大学邀请来自世界各地的人们作为客座学生。您可以来到贝尔兰的首都,与该国最好的老师一起学习。

伯兰州立大学每周每天都上课,但客座学生的课程按以下时间表举行。您知道七个整数的序列 $$$a_1, a_2, \dots, a_7$$$ ($$$a_i = 0$$$ 或 $$$a_i = 1$$$):

  • $$$a_1=1$$$ 当且仅当周日有客座学生上课;
  • $$$a_2=1$$$ 当且仅当周一有客座学生上课;
  • ...
  • $$$a_7=1$$$ 当且仅当周六有客座学生上课。

客座学生的课程每周至少有一天举行。

您想要访问伯兰首都,并在其中度过最少天数,作为伯兰州立大学的客座学生学习 $$$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$$$ 天的最短连续天数。

示例

输入
复制

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

注意

在第一个测试用例中,您必须在周一到达伯兰首都,在这一天上课,花一周时间直到下周一,并在下周一上课。您总共需要在伯兰州首都度过 $$$8$$$ 天。