#LUOGUP8987. [NERC2018] Guest Student

[NERC2018] Guest Student

题目背景

翻译自 NERC 2018 G 题。

题目描述

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

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

输入格式

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

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

然后 77 个整数 a1a7a_1 \sim a_7ai=1a_i = 1 表示有空,ai=0a_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

提示

对于所有数据,保证 1t100001 \leq t \leq 100001k1081 \leq k \leq 10^8ai{0,1}a_i \in \{0,1\}

对于样例一,从周二开始听课听到下周二,经过 88 天。