Sinh viên trao đổi

Trường Đại học Tổng hợp Berland nhận sinh viên trao đổi từ khắp nơi trên thế giới. Trường làm việc tất cả các ngày trong tuần, nhưng các lớp dành riêng cho sinh viên trao đổi chỉ diễn ra vào một số ngày cố định, lặp lại theo chu kỳ 7 ngày.

Lịch học được mô tả bởi bảy số nguyên $a_1,a_2,\dots ,a_7$ (mỗi $a_i$ bằng $0$ hoặc $1$):

• $a_1=1$ khi và chỉ khi có lớp vào Chủ nhật;
• $a_2=1$ khi và chỉ khi có lớp vào Thứ Hai;
• $\dots$
• $a_7=1$ khi và chỉ khi có lớp vào Thứ Bảy.

Đảm bảo có ít nhất một ngày trong tuần diễn ra lớp học.

Bạn muốn tới thủ đô Berland và ở lại một khoảng thời gian liên tiếp sao cho số ngày có lớp mà bạn tham dự đúng bằng $k$, đồng thời tổng số ngày lưu trú là nhỏ nhất. Bạn được tự do chọn ngày bắt đầu và ngày kết thúc của khoảng thời gian đó. Hãy tính độ dài nhỏ nhất của khoảng thời gian này.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $k$ là số ngày học cần đạt được.
  • Dòng thứ hai chứa đúng bảy số nguyên $a_1,a_2,\dots ,a_7$.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là đáp án cho bộ dữ liệu thứ $i$: độ dài nhỏ nhất của khoảng thời gian liên tiếp cần ở lại để tham dự đúng $k$ ngày học.

Ràng buộc

• $1\le t\le 10000$
• $1\le k\le {10}^8$
• $a_i\in \{0,1\}$ và $a_1+a_2+\cdots +a_7\ge 1$

Ví dụ