伯兰州立大学邀请来自世界各地的人们作为客座学生。您可以来到贝尔兰的首都,与该国最好的老师一起学习。
伯兰州立大学每周每天都上课,但客座学生的课程按以下时间表举行。您知道七个整数的序列 $$$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$$$ 天。