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.
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

import javax.print.attribute.HashAttributeSet;
import javax.swing.JLabel;

import java.io.PrintStream;
            
                public class Solution {

                    public static boolean Local(){
                        try{ 
                            return System.getenv("LOCAL_SYS")!=null;
                        }catch(Exception e){
                            return false;
                        }
                    }   

                    public static boolean LOCAL;

                    static class FastScanner {

                            BufferedReader br;
                            StringTokenizer st ;

                            FastScanner(){
                                br =  new BufferedReader(new InputStreamReader(System.in));
                                st = new StringTokenizer("");
                            }

                            FastScanner(String file) {

                                try{
                                    br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
                                    st = new StringTokenizer("");
                                }catch(FileNotFoundException e) {
                                    // TODO Auto-generated catch block
                                    System.out.println("file not found");
                                    e.printStackTrace();
                                }
                                
                            }
                            

                            String next() {
                                while (!st.hasMoreTokens())
                                    try {
                                        st = new StringTokenizer(br.readLine());
                                    } catch (IOException e) {
                                    }
                                return st.nextToken();
                            }

                            int nextInt() {
                                return Integer.parseInt(next());
                            }

                            long nextLong() {
                                return Long.parseLong(next());
                            }
                            String readLine() throws IOException{
                                return br.readLine();
                            }
                        }
                                            
                    static class Pair<T,X> {

                        T first;
                        X second;
                        
                        Pair(T first,X second){
                            this.first = first;
                            this.second = second;
                        }

                        @Override
                        public int hashCode(){
                            return Objects.hash(first,second);
                        }

                        @Override
                        public boolean equals(Object obj){
                            return obj.hashCode() == this.hashCode();
                        }

                    }

                
                static PrintStream debug = null;

                static long mod = (long)(Math.pow(10,9) + 7); 
                

                public static void main(String[] args) throws Exception {
                    
                    FastScanner s = new FastScanner();

                    LOCAL = Local();

                    
                    if(LOCAL){
                        s = new FastScanner("src/input.txt");
                        PrintStream o = new PrintStream("src/sampleout.txt");
                        debug = new PrintStream("src/debug.txt");
                        System.setOut(o);
                    }

                    long mod = 1000000007;
                
                    int tcr = s.nextInt();                  
                    
                    StringBuilder sb = new StringBuilder();

                    for(int tc=0;tc<tcr;tc++){
                        
                        int n = s.nextInt();

                        int d = s.nextInt();

                        int arr[] = new int[n];

                        Queue<Integer> q = new LinkedList<>();


                        for(int i=0;i<n;i++){
                            arr[i] = s.nextInt();
                            if(arr[i] == 0){q.add(i);}
                        }
                        q.add(null);
                        int cnt = 0;
                        while(q.size() > 0){
                            Integer curr = q.poll();
                            if(curr ==  null){
                                cnt++;
                                if(q.size() > 0){
                                    q.add(null);
                                }
                                continue;
                            }
                            int next = (curr + n - d) % n;
                            if(arr[next] != 0){
                                arr[next] = 0;
                                q.add(next);
                            }
                        }
                        boolean poss = true;
                        for(int i=0;i<n;i++){
                            if(arr[i] != 0){
                                poss = false;break;
                            }
                        }
                        if(poss){
                            sb.append((cnt-1)+"\n");
                        }else{
                            sb.append((-1)+"\n");
                        }


                    }

                    print(sb.toString());
                }
                public static List<long[]> prime_factors(long n){
            
                    List<long[]> list = new ArrayList<>();
                    
                    for(long i=2;i<=(Math.sqrt(n));i++){
            
                        if(n % i == 0){
                            
                            int cnt = 0;
                            
                            while( (n % i) == 0){
                                n = n/i;
                                cnt++;
                                
                            }
            
                            list.add(new long[]{i,cnt});
                        }
                    }

            
                    if(n!=1){
                        list.add(new long[]{n,1l});
                    }
            
                    return list;
            
                }

                public static boolean check(int arr[]){
                    for(int i=1;i<arr.length;i++){
                        if(arr[i] < arr[i-1]){
                            return false;
                        }
                    }
                    return true;
                }

            
                public static boolean inRange(int r1,int r2,int val){
                    return ((val >= r1) && (val <= r2));
                }

                static int len(long num){
                    return Long.toString(num).length();
                }

                static long mulmod(long a, long b,long mod)
                {
                    long ans = 0l;
                    
                    while(b > 0){
                        long curr = (b & 1l);
                        if(curr == 1l){
                            ans = ((ans % mod) + a) % mod;
                        }
                        
                        a = (a + a) % mod;

                        b = b >> 1;
                    }

                    return ans;
                }


                public static void dbg(PrintStream ps,Object... o) throws Exception{
                    if(ps == null){
                        return;
                    }
                    Debug.dbg(ps,o);
                }

                public static long modpow(long num,long pow,long mod){

                    long val = num;
                    long ans = 1l;

                    while(pow > 0l){
                        
                        long bit = pow & 1l;

                        if(bit == 1){
                            ans = (ans * (val%mod))%mod;
                        }

                        val = (val * val) % mod;
                        pow = pow >> 1;
                    }

                    return ans;

                }

                public static char get(int n){
                    return (char)('a' + n);
                }

                public static long[] sort(long arr[]){
                    List<Long> list = new ArrayList<>();
                    for(long n : arr){list.add(n);}
                    Collections.sort(list);
                    for(int i=0;i<arr.length;i++){
                        arr[i] = list.get(i);
                    }
                    return arr;
                }

                public static int[] sort(int arr[]){
                    List<Integer> list = new ArrayList<>();
                    for(int n : arr){list.add(n);}
                    Collections.sort(list);
                    for(int i=0;i<arr.length;i++){
                        arr[i] = list.get(i);
                    }
                    return arr;
                }

                // return the (index + 1)
                // where index is the pos of just smaller element
                // i.e count of elemets strictly less than num
                public static int justSmaller(long arr[],long num){
                    //  System.out.println(num+"@");
                    int st = 0;
                    int e = arr.length - 1;
            
                    int ans = -1;
            
                    while(st <= e){
            
                        int mid = (st + e)/2;
            
                        if(arr[mid] >= num){
                            e = mid - 1;
                        }else{
                            ans = mid;
                            st = mid + 1;
                        }
            
                    }
            
            
                    return ans + 1;
            
                }
                public static int justSmaller(int arr[],int num){
                    //  System.out.println(num+"@");
                    int st = 0;
                    int e = arr.length - 1;
            
                    int ans = -1;
            
                    while(st <= e){
            
                        int mid = (st + e)/2;
            
                        if(arr[mid] >= num){
                            e = mid - 1;
                        }else{
                            ans = mid;
                            st = mid + 1;
                        }
            
                    }
            
            
                    return ans + 1;
            
                }
                
                //return (index of just greater element)
                //count of elements smaller than or equal to num

                public static int justGreater(long arr[],long num){
                    int st = 0;
                    int e = arr.length - 1;
            
                    int ans = arr.length;
            
                    while(st <= e){
                        
                        int mid = (st + e)/2;
            
                        if(arr[mid] <= num){
                            st = mid + 1;
                        }else{
                            ans = mid;
                            e = mid - 1;
                        }
                    }
            
                    return ans;
            
                }

                public static int justGreater(int arr[],int num){
                    int st = 0;
                    int e = arr.length - 1;
            
                    int ans = arr.length;
            
                    while(st <= e){
                        
                        int mid = (st + e)/2;
            
                        if(arr[mid] <= num){
                            st = mid + 1;
                        }else{
                            ans = mid;
                            e = mid - 1;
                        }
                    }
            
                    return ans;
            
                }
            
                

                public static void println(Object obj){
                    System.out.println(obj.toString());
                }

                public static void print(Object obj){
                    System.out.print(obj.toString());
                }

                public static int gcd(int a,int b){
                    if(b == 0){return a;}
                    return gcd(b,a%b);
                }

                public static long gcd(long a,long b){
                    if(b == 0l){
                        return a;
                    }

                    return gcd(b,a%b);
                }

                public static int find(int parent[],int v){
                    if(parent[v] == v){
                        return v;
                    }
                    
                    return parent[v] = find(parent, parent[v]);
                }

            

                public static List<Integer> sieve(){
                
                        List<Integer> prime = new ArrayList<>();

                        int arr[] = new int[100001];

                    Arrays.fill(arr,1);

                    arr[1] = 0;
                    arr[2] = 1;

                    for(int i=2;i<=100000;i++){
                        
                        if(arr[i] == 1){
                            
                            prime.add(i);

                            for(long j = (i*1l*i);j<100001;j+=i){
                                arr[(int)j] = 0;
                            }
                        }
                    }

                    return prime;
                }

                static boolean isPower(long n,long a){
                    
                    long log = (long)(Math.log(n)/Math.log(a));

                    long power = (long)Math.pow(a,log);

                    if(power == n){return true;}

                    return false;
                }


                private static int mergeAndCount(int[] arr, int l,int m, int r)
                {

                    // Left subarray
                    int[] left =  Arrays.copyOfRange(arr, l, m + 1);

                    // Right subarray
                    int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

                    int i = 0, j = 0, k = l, swaps = 0;

                    while (i < left.length && j < right.length) {
                        if (left[i] <= right[j])
                            arr[k++] = left[i++];
                        else {
                            arr[k++] = right[j++];
                            swaps += (m + 1) - (l + i);
                        }
                    }
                    while (i < left.length)
                        arr[k++] = left[i++];
                    while (j < right.length)
                        arr[k++] = right[j++];
                    return swaps;
                }

                // Merge sort function
                private static int mergeSortAndCount(int[] arr, int l,int r)
                {

                    // Keeps track of the inversion count at a
                    // particular node of the recursion tree
                    int count = 0;

                    if (l < r) {
                        int m = (l + r) / 2;

                        // Total inversion count = left subarray count
                        // + right subarray count + merge count

                        // Left subarray count
                        count += mergeSortAndCount(arr, l, m);

                        // Right subarray count
                        count += mergeSortAndCount(arr, m + 1, r);

                        // Merge count
                        count += mergeAndCount(arr, l, m, r);
                    }

                    return count;
                }

                static class Debug{
                    //change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
                    public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;

                    

                    private static <T> String ts(T t) {
                        if(t==null) {
                            return "null";
                        }
                        try {
                            return ts((Iterable) t);
                        }catch(ClassCastException e) {
                            if(t instanceof int[]) {
                                String s = Arrays.toString((int[]) t);
                                return "{"+s.substring(1, s.length()-1)+"}\n";
                            }else if(t instanceof long[]) {
                                String s = Arrays.toString((long[]) t);
                                return "{"+s.substring(1, s.length()-1)+"}\n";
                            }else if(t instanceof char[]) {
                                String s = Arrays.toString((char[]) t);
                                return "{"+s.substring(1, s.length()-1)+"}\n";
                            }else if(t instanceof double[]) {
                                String s = Arrays.toString((double[]) t);
                                return "{"+s.substring(1, s.length()-1)+"}\n";
                            }else if(t instanceof boolean[]) {
                                String s = Arrays.toString((boolean[]) t);
                                return "{"+s.substring(1, s.length()-1)+"}\n";
                            }
                            try {
                                return ts((Object[]) t);
                            }catch(ClassCastException e1) {
                                return t.toString();
                            }
                        }
                    }
                    private static <T> String ts(T[] arr) {
                        StringBuilder ret = new StringBuilder();
                        ret.append("{");
                        boolean first = true;
                        for(T t: arr) {
                            if(!first) {
                                ret.append(", ");
                            }
                            first = false;
                            ret.append(ts(t));
                        }
                        ret.append("}");
                        return ret.toString();
                    }
                    private static <T> String ts(Iterable<T> iter) {
                        StringBuilder ret = new StringBuilder();
                        ret.append("{");
                        boolean first = true;
                        for(T t: iter) {
                            if(!first) {
                                ret.append(", ");
                            }
                            first = false;
                            ret.append(ts(t));
                        }
                        ret.append("}");
                        return ret.toString();
                    }
                    public static void dbg(PrintStream ps,Object... o) throws Exception {
                        if(LOCAL) {
                            System.setErr(ps);
                            System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
                            for(int i = 0; i<o.length; i++) {
                                if(i!=0) {
                                    System.err.print(", ");
                                }
                                System.err.print(ts(o[i]));
                            }
                            System.err.println("]");
                        }
                    }
                }

        }


        