교환 학생

베를란트 국립 대학은 전 세계에서 교환 학생을 받는다. 베를란트의 수도에 가서 그 나라 최고의 교사들에게 배울 수 있다.

베를란트 국립 대학은 주 7일 내내 문을 열지만, 교환 학생을 위한 수업은 다음 일정에 따라 열린다. 일곱 개의 정수 $a_1, a_2, \ldots, a_7$ ($a_i = 0$ 또는 $a_i = 1$)이 주어진다.

• 일요일에 교환 학생 수업이 있으면 $a_1 = 1$이고, 없으면 $a_1 = 0$이다.
• 월요일에 교환 학생 수업이 있으면 $a_2 = 1$이고, 없으면 $a_2 = 0$이다.
• ...
• 토요일에 교환 학생 수업이 있으면 $a_7 = 1$이고, 없으면 $a_7 = 0$이다.

교환 학생 수업은 일주일 중 적어도 하루에는 열린다.

베를란트 국립 대학에서 교환 학생으로 $k$일 동안 공부하기 위해, 수도에 머무는 날짜 수를 최소로 하고 싶다. 교환 학생으로 정확히 $k$일 공부하기 위해 수도에 연속으로 머물러야 하는 최소 일수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 10\,000$). 각 테스트 케이스마다 문제를 독립적으로 풀고 답을 출력한다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 교환 학생으로 공부해야 하는 날짜 수 $k$가 주어진다 ($1 \le k \le 10^8$). 둘째 줄에는 정확히 일곱 개의 정수 $a_1, a_2, \ldots, a_7$이 주어진다 ($a_i = 0$ 또는 $a_i = 1$). $a_i = 1$이면 일주일 중 $i$번째 날에 교환 학생 수업이 열린다.

$t$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스의 답, 즉 교환 학생으로 정확히 $k$일 공부하기 위해 머물러야 하는 최소 연속 일수를 출력한다.

첫 번째 테스트 케이스에서는 월요일에 베를란트의 수도에 도착해서 그날 수업을 듣고, 다음 월요일까지 일주일을 보낸 뒤 다음 월요일에 다시 수업을 들어야 한다. 따라서 베를란트의 수도에 총 8일을 머물러야 한다.