description: You are given an array a[0 … n - 1] = [a_0, a_1, …, a_{n - 1}] of zeroes and ones only. Note that in this problem, unlike the others, the array indexes are numbered from zero, not from one.
  
  In one step, the array a is replaced by another array of length n according to the following rules: 
  
    1. First, a new array a^{→ d} is defined as a cyclic shift of the array a to the right by d cells. The elements of this array can be defined as a^{→ d}_i = a_{(i + n - d) mod n}, where (i + n - d) mod n is the remainder of integer division of i + n - d by n. 
  
  It means that the whole array a^{→ d} can be represented as a sequence $$$a^{→ d} = [a_{n - d}, a_{n - d + 1}, …, a_{n - 1}, a_0, a_1, …, a_{n - d - 1}]$$$
  
    2. Then each element of the array a_i is replaced by a_i  \&  a^{→ d}_i, where \& is a logical "AND" operator. 
  
  
  
  For example, if a = [0, 0, 1, 1] and d = 1, then a^{→ d} = [1, 0, 0, 1] and the value of a after the first step will be [0  \&  1, 0  \&  0, 1  \&  0, 1  \&  1], that is [0, 0, 0, 1].
  
  The process ends when the array stops changing. For a given array a, determine whether it will consist of only zeros at the end of the process. If yes, also find the number of steps the process will take before it finishes.
  
  Input
  
  The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.
  
  The next 2t lines contain descriptions of the test cases. 
  
  The first line of each test case description contains two integers: n (1 ≤ n ≤ 10^6) — array size and d (1 ≤ d ≤ n) — cyclic shift offset. The second line of the description contains n space-separated integers a_i (0 ≤ a_i ≤ 1) — elements of the array.
  
  It is guaranteed that the sum of n over all test cases does not exceed 10^6.
  
  Output
  
  Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the number of steps after which the array will contain only zeros for the first time. If there are still elements equal to 1 in the array after the end of the process, print -1.
  
  Example
  
  Input
  
  
  5
  2 1
  0 1
  3 2
  0 1 0
  5 2
  1 1 0 1 0
  4 2
  0 1 0 1
  1 1
  0
  
  
  Output
  
  
  1
  1
  3
  -1
  0
  
  Note
  
  In the third sample test case the array will change as follows: 
  
    1. At the beginning a = [1, 1, 0, 1, 0], and a^{→ 2} = [1, 0, 1, 1, 0]. Their element-by-element "AND" is equal to $$$[1  \&  1, 1  \&  0, 0  \&  1, 1  \&  1, 0  \&  0] = [1, 0, 0, 1, 0]$$$ 
    2. Now a = [1, 0, 0, 1, 0], then a^{→ 2} = [1, 0, 1, 0, 0]. Their element-by-element "AND" equals to $$$[1  \&  1, 0  \&  0, 0  \&  1, 1  \&  0, 0  \&  0] = [1, 0, 0, 0, 0]$$$ 
    3. And finally, when a = [1, 0, 0, 0, 0] we get a^{→ 2} = [0, 0, 1, 0, 0]. Their element-by-element "AND" equals to $$$[1  \&  0, 0  \&  0, 0  \&  1, 0  \&  0, 0  \&  0] = [0, 0, 0, 0, 0]$$$ 
  
  Thus, the answer is 3 steps.
  
  In the fourth sample test case, the array will not change as it shifts by 2 to the right, so each element will be calculated as 0  \&  0 or 1  \&  1 thus not changing its value. So the answer is -1, the array will never contain only zeros.
solution: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.PrintWriter;
  import java.util.Arrays;
  import java.util.InputMismatchException;
  import java.io.IOException;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
  
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader in = new InputReader(inputStream);
          PrintWriter out = new PrintWriter(outputStream);
          FStabiliziruiMassivIVersiya solver = new FStabiliziruiMassivIVersiya();
          int testCount = Integer.parseInt(in.next());
          for (int i = 1; i <= testCount; i++) {
              solver.solve(i, in, out);
          }
          out.close();
      }
  
      static class FStabiliziruiMassivIVersiya {
  
          int doit(int pos, int d, int[] mem, int[] a) {
              if (a[pos] == 0) {
                  return 0;
              }
  
              if (mem[pos] == -2) {
                  return -2;
              }
              if (mem[pos] != -1) {
                  return mem[pos];
              }
  
              mem[pos] = -2;
              int val = doit((pos + mem.length - d) % mem.length, d, mem, a);
              if (val == -2) {
                  return -2;
              }
              mem[pos] = val + 1;
  
              return mem[pos];
          }
  
          public void solve(int testNumber, InputReader in, PrintWriter out) {
              int n = in.nextInt();
              int d = in.nextInt();
              int[] a = new int[n];
              for (int i = 0; i < n; i++) {
                  a[i] = in.nextInt();
              }
              int[] mem = new int[n];
              Arrays.fill(mem, -1);
              int max = Integer.MIN_VALUE;
              for (int i = 0; i < n; i++) {
                  int val = doit(i, d, mem, a);
                  if (val == -2) {
                      out.println(-1);
                      return;
                  }
                  max = Math.max(max, val);
              }
              out.println(max);
          }
      }
  
      static class InputReader {
  
          private static final int BUFFER_LENGTH = 1 << 10;
          private InputStream stream;
          private byte[] buf = new byte[BUFFER_LENGTH];
          private int curChar;
          private int numChars;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          private int nextC() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar++];
          }
  
          public String next() {
              int c = nextC();
              while (isSpaceChar(c)) {
                  c = nextC();
              }
              StringBuilder res = new StringBuilder();
              do {
                  res.append((char) c);
                  c = nextC();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          public int nextInt() {
              int c = skipWhileSpace();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = nextC();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = nextC();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public int skipWhileSpace() {
              int c = nextC();
              while (isSpaceChar(c)) {
                  c = nextC();
              }
              return c;
          }
  
          public boolean isSpaceChar(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
      }
  }
  
  