Ổn định mảng (phép AND)

Cho một mảng $a[0\dots n-1]$ gồm các phần tử $0$ hoặc $1$ (chỉ số bắt đầu từ $0$).

Trong một bước, mảng $a$ được thay bằng một mảng mới có cùng độ dài theo quy tắc sau:

1. Đầu tiên, định nghĩa $a^{\to d}$ là mảng $a$ sau khi dịch vòng sang phải $d$ ô, tức là $a_i^{\to d}=a_{(i+n-d)modn}$.
2. Sau đó mỗi phần tử $a_i$ được thay bằng $a_i<mrow><mi>\&</mi></mrow>a_i^{\to d}$, trong đó $\&$ là phép AND logic.

Quá trình kết thúc khi mảng không còn thay đổi. Với mảng $a$ cho trước, hãy xác định xem cuối cùng mảng có gồm toàn số $0$ hay không. Nếu có, in ra số bước cần thiết; nếu không, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 1000$) — số bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa hai số nguyên $n$ và $d$ ($1\le n\le {10}^6$, $1\le d\le n$).
  • Dòng thứ hai chứa $n$ số nguyên $a_i$ ($0\le a_i\le 1$).

Tổng $n$ trên tất cả các bộ test không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên trên một dòng: số bước nhỏ nhất để mảng trở thành toàn $0$, hoặc $-1$ nếu điều đó không thể xảy ra.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le {10}^6$
• $1\le d\le n$
• $0\le a_i\le 1$
• $\sum n\le {10}^6$

Ví dụ