You are given an array $a[0 \ldots n - 1] = [a_0, a_1, \ldots, 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:

First, a new array $a^{\rightarrow 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^{\rightarrow 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^{\rightarrow d}$ can be represented as a sequence $$a^{\rightarrow d} = [a_{n - d}, a_{n - d + 1}, \ldots, a_{n - 1}, a_0, a_1, \ldots, a_{n - d - 1}]$$

Then each element of the array $a_i$ is replaced by $a_i \,\&\, a^{\rightarrow d}_i$, where $\&$ is a logical "AND" operator.

For example, if $a = [0, 0, 1, 1]$ and $d = 1$, then $a^{\rightarrow 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 \leq t \leq 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 \le n \le 10^6$) — array size and $d$ ($1 \le d \le n$) — cyclic shift offset. The second line of the description contains $n$ space-separated integers $a_i$ ($0 \le a_i \le 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.


-----Examples-----

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:

At the beginning $a = [1, 1, 0, 1, 0]$, and $a^{\rightarrow 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]$$

Now $a = [1, 0, 0, 1, 0]$, then $a^{\rightarrow 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]$$

And finally, when $a = [1, 0, 0, 0, 0]$ we get $a^{\rightarrow 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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Shortest paths

Complete search

Number theory

Mathematics


Solutions:
import sys
INF = float('inf')
mod = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def li():
	return list(map(int, input().split()))
T = int(input())
for _ in range(T):
	(N, D) = li()
	A = li()
	if D == N:
		if 1 in A:
			print(-1)
		else:
			print(0)
		continue
	x = 0
	lst = [0]
	se = set([0])
	while True:
		x += D
		x %= N
		if x in se:
			break
		lst.append(x)
		se.add(x)
	ans = 0
	seen = set()
	for i in range(N):
		if i in seen:
			continue
		cnt = 0
		seen.add(i)
		for j in range(len(lst) * 2):
			a = (lst[j % len(lst)] + i) % N
			seen.add(a)
			if A[a] == 1:
				cnt += 1
				ans = max(ans, cnt)
			else:
				cnt = 0
	if ans > len(lst):
		ans = -1
	print(ans)


from collections import deque

def cycle_detectable_topological_sort(g, ind):
	V = len(g)
	order = []
	depth = [-1] * V
	for i in range(V):
		if not ind[i]:
			order.append(i)
			depth[i] = 0
	q = deque(order)
	while q:
		v = q.popleft()
		cur_depth = depth[v]
		for u in g[v]:
			ind[u] -= 1
			if not ind[u]:
				depth[u] = max(depth[u], cur_depth + 1)
				q.append(u)
				order.append(u)
	if len(order) == V:
		return (order, depth)
	else:
		return (None, None)
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	A = list(map(int, input().split()))
	if sum(A) == 0:
		print(0)
		continue
	g = [[] for i in range(n)]
	rg = [[] for i in range(n)]
	ind = [0] * n
	for (i, a) in enumerate(A):
		j = (i + d) % n
		if a == 1 and A[j] == 1:
			g[i].append(j)
			rg[j].append(i)
			ind[j] += 1
	(order, _) = cycle_detectable_topological_sort(g, ind)
	if order is None:
		print(-1)
		continue
	order.reverse()
	dp = [1] * n
	for v in order:
		for u in rg[v]:
			dp[u] = max(dp[u], dp[v] + 1)
	print(max(dp))


import os, sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda dtype: [dtype(x) for x in input().split()]
inp_2d = lambda dtype, n: [dtype(input()) for _ in range(n)]
inp_2ds = lambda dtype, n: [inp(dtype) for _ in range(n)]
inp_enu = lambda dtype: [(i, x) for (i, x) in enumerate(inp(dtype))]
inp_enus = lambda dtype, n: [[i] + inp(dtype) for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
for _ in range(int(input())):
	(n, d) = inp(int)
	a = inp(int)
	(d, ans, vis) = (n - d, 0, [-1] * n)
	for i in range(n):
		(ix, val, tem, flag) = (i, a[i], 0, 1)
		(stk, cost) = ([ix], 0)
		while val:
			if ix == i and (not flag):
				flag = -1
				break
			if vis[ix] != -1:
				cost = vis[ix]
				break
			tem += 1
			flag = 0
			ix = (ix + d) % n
			val &= a[ix]
			stk.append(ix)
		if flag == -1:
			ans = -1
			break
		ans = max(ans, tem + cost)
		while stk:
			vis[stk.pop()] = tem + cost
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	(n, d) = map(int, input().split())
	(*a,) = map(int, input().split())
	q = []
	w = [int(1000000000.0)] * n
	for i in range(n):
		if a[i] == 0:
			q.append(i)
			w[i] = 0
	i = 0
	while i < len(q):
		x = q[i]
		i += 1
		y = (x + d) % n
		if w[y] > n:
			w[y] = w[x] + 1
			q.append(y)
	r = max(w)
	if r > n:
		print(-1)
	else:
		print(r)
for i in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	ar = list(map(int, input().split()))
	se = set({})
	li = []
	for i in range(n):
		if not i in se:
			li.append([ar[i]])
			se.add(i)
			j = (i + d) % n
			while j != i:
				li[-1].append(ar[j])
				se.add(j)
				j = (j + d) % n
			li[-1] = li[-1] + li[-1]
	ans = 0
	flag = True
	for i in li:
		le = len(i)
		count = i.count(1)
		if count == le:
			flag = False
			break
		count = 0
		for j in i:
			if j == 1:
				count += 1
			else:
				count = 0
			ans = max(ans, count)
	if flag:
		print(ans)
	else:
		print(-1)


def find(x):
	if par[x] == x:
		return par[x]
	par[x] = find(par[x])
	return par[x]

def union(x, y):
	px = find(x)
	py = find(y)
	if px != py:
		if count[px] > count[py]:
			(px, py) = (py, px)
		par[px] = par[py]
		count[py] += count[px]
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	m = n
	arr = list(map(int, input().split()))
	if max(arr) == 0:
		print(0)
		continue
	vis = [False for i in range(n + 1)]
	par = [i for i in range(n)]
	count = [0 for i in range(n)]
	for i in range(n):
		if arr[i] == 1:
			vis[i] = True
	flag = 0
	for i in range(n):
		if vis[i] == True and vis[(i - d) % m] == True:
			if find(i) == find((i - d) % m):
				flag = -1
				break
			union(i, (i - d) % m)
	if flag == -1:
		print(-1)
		continue
	for i in range(n):
		par[i] = find(i)
	d = {}
	for i in range(n):
		if par[i] in d:
			d[par[i]] += 1
		else:
			d[par[i]] = 1
	maxi = 0
	for i in d:
		maxi = max(maxi, d[i])
	print(maxi)


import sys
tokens = ''.join(sys.stdin.readlines()).split()[::-1]

def next():
	return tokens.pop()

def nextInt():
	return int(next())

def nextFloat():
	return float(next())

def getIntArray(n):
	return [nextInt() for _ in range(n)]

def getFloatArray(n):
	return [nextFloat() for _ in range(n)]

def getStringArray(n):
	return [next() for _ in range(n)]
testcase = True

def solve(testcase=1):
	pass
	(N, D) = (nextInt(), nextInt())
	A = getIntArray(N)
	count = 0
	vis = [False for i in range(N)]
	for i in range(N):
		if not vis[i] and (not A[i]):
			j = (i - D) % N
			temp = 0
			while A[j] and (not vis[j]):
				vis[j] = True
				j = (j - D) % N
				temp += 1
			count = max(count, temp)
			vis[i] = True
	print(count if all(vis) else -1)
if testcase is None:
	testcaseCount = 1
	while tokens:
		solve(testcaseCount)
		testcaseCount += 1
else:
	testcaseCount = nextInt() if testcase else 1
	for tc in range(testcaseCount):
		solve(tc + 1)
	assert not tokens


from itertools import groupby
from math import gcd
from sys import stdout
output = []
for _t in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	if d == n:
		output.append(-1 if any((num == 1 for num in a)) else 0)
		continue
	max_size = n // gcd(n, d)
	limit = n * d // gcd(n, d) * 2
	max_run = max((max((sum((1 for e in group)) for (key, group) in groupby((a[j % n] for j in range(start, limit, d))) if key == 1), default=0) for start in range(gcd(n, d))))
	output.append(-1 if max_run >= max_size else max_run)
stdout.write('\n'.join(map(str, output)))


DEBUG = False

def solve(N, D, nums):
	seen = [False] * N
	res = 0
	for i in range(N):
		if seen[i]:
			continue
		seen[i] = True
		if DEBUG:
			print(f'\nStart cycle from i={i}')
		first0 = 0 if nums[i] == 0 else -1
		last1 = 0 if nums[i] == 1 else -1
		mx = 0
		(j, cnt) = (i, 0)
		while True:
			j = (j + D) % N
			seen[j] = True
			cnt += 1
			if DEBUG:
				print(f'j={j}: cnt={cnt}, last1={last1}, mx={mx}')
			if nums[j] == 1:
				if last1 < 0:
					last1 = cnt
			else:
				if first0 == -1:
					first0 = cnt
				if last1 != -1:
					mx = max(mx, cnt - last1)
					last1 = -1
			if j == i:
				break
		if DEBUG:
			print(f'Finish: mx={mx}, last1={last1}, first0={first0}, cnt={cnt}')
		if last1 != -1:
			if first0 == -1:
				return -1
			mx = max(mx, (first0 - last1 + cnt) % cnt)
		res = max(res, mx)
	return res

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, D) = map(int, stdin.readline().strip().split())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, D, nums)
		print(out)
main()


from math import gcd
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	a = [int(x) for x in input().split()]
	g = gcd(n, d)
	ands = [1] * g
	for i in range(n):
		ands[i % g] &= a[i]
	if 1 in ands:
		print(-1)
		continue
	most = 0
	for k in range(g):
		curr = k
		last0 = -1
		i = 0
		steps = {}
		seen = False
		while not curr in steps:
			if seen and curr == k and (a[curr] == 0) and (len(steps) == 0):
				break
			if a[curr] == 0:
				last0 = i
			elif last0 != -1:
				steps[curr] = i - last0
			curr += d
			curr %= n
			seen = True
			i += 1
		for (_, v) in steps.items():
			most = max(most, v)
	print(most)


def ones(arr):
	if not any((v == 0 for v in arr)):
		return -1
	zero_i = arr.index(0)
	arr = arr[zero_i:] + arr[:zero_i] + [0]
	(best, tmp) = (0, 0)
	for v in arr:
		if v:
			tmp += 1
		else:
			best = max(best, tmp)
			tmp = 0
	return best
for t in range(int(input())):
	(n, d) = tuple(map(int, input().rstrip().split()))
	arr = tuple(map(int, input().rstrip().split()))
	best = 0
	done = [False] * n
	for i in range(n):
		if done[i]:
			continue
		done[i] = True
		tmp = [arr[i]]
		j = (i + d) % n
		while j != i:
			tmp.append(arr[j])
			done[j] = True
			j = (j + d) % n
		tmp = ones(tmp)
		if tmp == -1:
			best = -1
			break
		best = max(best, tmp)
	print(best)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	paths = []
	d = n - d
	s = set()
	for i in range(n):
		if i in s:
			continue
		path = []
		path.append(l[i])
		s.add(i)
		j = (i + d) % n
		while j < n and j not in s:
			path.append(l[j])
			s.add(j)
			j = (j + d) % n
		paths.append(path + path)
	ans = 0
	for path in paths:
		i = 0
		n1 = len(path)
		if 0 not in path:
			ans = -1
			break
		while i < n1:
			if path[i] == 0:
				i += 1
				continue
			else:
				j = i + 1
				while j < n1 and path[j] == 1:
					j += 1
				ans = max(j - i, ans)
				i = j
	print(ans)


import sys
import math
from math import factorial, inf, gcd, sqrt
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
from bisect import *
import random
from sys import stdin, stdout
sys.setrecursionlimit(10 ** 5)

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def mp():
	return map(int, inp().split())

def lmp():
	return list(mp())
t = iinp()
for i in range(t):
	(n, d) = mp()
	a = lmp()
	ans = -1
	f = [False] * n
	for i in range(n):
		if not f[i]:
			c = [i]
			f[i] = True
			j = (n - d + i) % n
			while j != c[0]:
				f[j] = True
				c.append(j)
				j = (n - d + j) % n
			c = [a[i] for i in c]
			if 0 not in c:
				ans = -1
				break
			m = len(c)
			j = c.index(0)
			res = j
			for i in range(1, m):
				c.append(c[i - 1])
				j = max(j, i)
				while j < len(c) and c[j] == 1:
					j += 1
				res = max(res, j - i)
			ans = max(ans, res)
	print(ans)


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
for _ in range(rn()):
	(n, d) = rns()
	a = rl()
	loops = []
	seen = set()
	ans = 0
	for i in range(n):
		if i in seen:
			break
		seen.add(i)
		loop = [a[i]]
		j = (i - d) % n
		while j != i:
			seen.add(j)
			loop.append(a[j])
			j = (j - d) % n
		loops.append(loop)
	for loop in loops:
		if 0 not in loop:
			ans = -1
			break
		i = loop.index(0)
		loop = loop[i:] + loop[:i]
		curr = 0
		for i in range(1, len(loop)):
			if loop[i] == 1:
				curr += 1
			else:
				curr = 0
			ans = max(ans, curr)
	print(ans)


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]

	def A2(n, m):
		return [[0] * m for i in range(n)]

	def A(n):
		return [0] * n
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
for _ in range(L()[0]):
	(n, d) = L()
	A = L()
	dist = [-A[i] for i in range(n)]
	changed = 10
	while changed:
		changed = 0
		for i in range(n):
			if dist[(i - d) % n] != -1 and dist[i] == -1:
				dist[i] = dist[(i - d) % n] + 1
				changed = 1
	if -1 in dist:
		print(-1)
	else:
		print(max(dist))


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(n, k) = R()
	a = L()
	flg = False
	ans = 0
	for i in range(n):
		if a[i] == -1:
			continue
		flg = True
		j = i
		v = []
		while a[j % n] != -1:
			v += (a[j % n],)
			if not a[j % n]:
				flg = False
			a[j % n] = -1
			j += k
		if flg:
			break
		p = v.index(0)
		m = 0
		ln = len(v)
		while v[p % ln] != -1:
			if v[p % ln]:
				m += 1
				ans = max(ans, m)
			else:
				m = 0
			v[p % ln] = -1
			p += 1
	print(-1 if flg else ans)


from collections import deque
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	maxx = [0 if arr[i] == 0 else 10 ** 9 for i in range(n)]
	queue = deque([i for i in range(n) if arr[i] == 0])
	while len(queue):
		node = queue.popleft()
		zero = (node + d) % n
		if maxx[zero] > n:
			maxx[zero] = maxx[node] + 1
			queue.append(zero)
	print(-1 if max(maxx) > n else max(maxx))


import sys
from sys import stdin
from collections import deque
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(n, D) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	d = [float('inf')] * n
	q = deque()
	for i in range(n):
		if a[i] == 0:
			q.append(i)
			d[i] = 0
	while q:
		v = q.popleft()
		nex = (v + D) % n
		if d[nex] > d[v] + 1:
			d[nex] = d[v] + 1
			q.append(nex)
	ans = 0
	for i in range(n):
		ans = max(ans, d[i])
	if ans == float('inf'):
		ANS.append('-1')
	else:
		ANS.append(str(ans))
print('\n'.join(ANS))


import sys
input = sys.stdin.readline

def check_zero(a, seen, i, n, d):
	zero = -1
	while not seen[i]:
		seen[i] = True
		if a[i] == 0:
			zero = i
		i = (i + d) % n
	return zero

def check_run(a, i, n, d):
	j = (i + d) % n
	max_run = 0
	cur_run = 0
	while j != i:
		if a[j] == 1:
			cur_run += 1
			max_run = max(max_run, cur_run)
		else:
			cur_run = 0
		j = (j + d) % n
	return max_run
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = [int(i) for i in input().split()]
	seen = [False] * n
	ok = True
	max_run = 0
	for i in range(n):
		if not seen[i]:
			zero = check_zero(a, seen, i, n, d)
			if zero == -1:
				ok = False
				break
			else:
				max_run = max(max_run, check_run(a, zero, n, d))
	print(max_run if ok else -1)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	array = [int(entry) for entry in input().split()]
	visited = [False for j in range(n)]
	block_size = 0
	res = 0
	max_block_size = 0
	fail = False
	for idx in range(n):
		if visited[idx]:
			continue
		block_idx = idx
		block_size = 0
		max_block_size = 0
		(pref, iterations) = (0, 0)
		while True:
			visited[block_idx] = True
			if array[block_idx] == 1:
				block_size += 1
				if iterations == pref:
					pref += 1
			else:
				max_block_size = max(max_block_size, block_size)
				block_size = 0
			block_idx = (block_idx + d) % n
			iterations += 1
			if block_idx == idx:
				break
		if iterations != pref:
			max_block_size = max(max_block_size, pref + block_size)
		else:
			fail = True
			break
		res = max(res, max_block_size)
	if fail:
		print('-1')
	else:
		print(res)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	q = []
	w = [int(1000000000.0)] * n
	for i in range(n):
		if a[i] == 0:
			q.append(i)
			w[i] = 0
	i = 0
	while i < len(q):
		x = q[i]
		i += 1
		y = (x + d) % n
		if w[y] > n:
			w[y] = w[x] + 1
			q.append(y)
	r = max(w)
	if r > n:
		print(-1)
	else:
		print(r)


def naiveSolve():
	return

def solve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, d) = readIntArr()
		a = readIntArr()
		if len(set(a)) == 1:
			if a[0] == 1:
				allans.append(-1)
			else:
				allans.append(0)
			continue
		if d == n:
			allans.append(-1)
			continue
		eventualVal = [1] * n
		nSteps = [-1] * n
		vi = [False] * n
		for (i, x) in enumerate(a):
			if x == 0:
				eventualVal[i] = 0
				nSteps[i] = 0
				vi[i] = True
		for i in range(n):
			if not vi[i]:
				j = (i + d) % n
				steps = 1
				finalVal = 1
				while i != j and a[j] == 1 and (vi[j] == False):
					j = (j + d) % n
					steps += 1
				if vi[j]:
					finalVal = eventualVal[j]
					steps += nSteps[j]
				else:
					finalVal = a[j]
				j = i
				while steps > 0:
					eventualVal[j] = finalVal
					vi[j] = True
					nSteps[j] = steps
					steps -= 1
					j = (j + d) % n
		if 1 in eventualVal:
			allans.append(-1)
		else:
			allans.append(max(nSteps))
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
for _ in range(int(sys.stdin.readline())):
	(n, d) = [int(i) for i in sys.stdin.readline().split()]
	a = [int(i) for i in sys.stdin.readline().split()][:n]
	m = 0
	for i in range(n):
		if a[i] == 1 and a[(i + n - d) % n] == 0:
			a[i] = 0
			c = 1
			j = i
			while a[(j + d) % n] == 1:
				c += 1
				j = (j + d) % n
				a[j] = 0
			if c > m:
				m = c
	sys.stdout.write('%d\n' % (-1 if any(a) else m))


import decimal
import heapq
import math
import os
import sys
from io import BytesIO, IOBase
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ints_get():
	return map(int, input().strip().split())

def list_get():
	return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
	return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def ipn():
	return int(input())

def main():
	for _ in range(ipn()):
		(n, d) = ints_get()
		a = list_get()
		s = set([])
		for i in range(n):
			s.add(i)
		v = []
		while len(s) > 0:
			p = []
			e = s.pop()
			p.append(a[e])
			while True:
				e += d
				e %= n
				if e not in s:
					break
				else:
					p.append(a[e])
					s.remove(e)
			v.append(p)
		for i in v:
			if i.count(0) == 0:
				print(-1)
				break
		else:
			ma = 0
			for i in v:
				k = []
				val = 0
				for l in i:
					if l == 1:
						val += 1
					elif val > 0:
						k.append(val)
						val = 0
				if val > 0:
					k.append(val)
				if i[0] == 1 and i[-1] == 1:
					k.append(k[0] + k[-1])
				if len(k) == 0:
					continue
				ma = max(max(k), ma)
			output(ma)
	return
main()


def solve_orig(N, D, nums):
	seen = [False] * N
	res = 0
	for i in range(N):
		if seen[i]:
			continue
		seen[i] = True
		first0 = 0 if nums[i] == 0 else -1
		last1 = 0 if nums[i] == 1 else -1
		mx = 0
		(j, ln) = (i, 0)
		while True:
			j = (j + D) % N
			seen[j] = True
			ln += 1
			if nums[j] == 1:
				if last1 < 0:
					last1 = ln
			else:
				if first0 == -1:
					first0 = ln
				if last1 != -1:
					mx = max(mx, ln - last1)
					last1 = -1
			if j == i:
				break
		if last1 != -1:
			if first0 == -1:
				return -1
			mx = max(mx, (first0 - last1 + ln) % ln)
		res = max(res, mx)
	return res

def solve(N, D, nums):
	seen = [False] * N
	res = 0
	for i in range(N):
		if seen[i]:
			continue
		orig = i
		first = -1
		cnt = 0
		has_zero = False
		key = -1
		while True:
			i = (i + D) % N
			seen[i] = True
			if nums[i] != key and key != -1:
				if key == 1:
					res = max(res, cnt)
				if first < 0:
					first = cnt if key == 1 else 0
				cnt = 0
			key = nums[i]
			cnt += 1
			if key == 0:
				has_zero = True
			if i == orig:
				break
		if key == 1:
			res = max(res, cnt + first)
		if not has_zero:
			return -1
	return res

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, D) = map(int, stdin.readline().strip().split())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(N, D, nums)
		print(out)
main()


import math
t = int(input())
for _ in range(t):
	(n, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	g = math.gcd(n, d)
	gg = 2 * n // g
	ans = 0
	for i in range(g):
		j = i
		k = 0
		longest_run = 0
		ones = 0
		while k < gg:
			if arr[j] == 1:
				ones += 1
			else:
				ones = 0
			longest_run = max(ones, longest_run)
			j = (j + d) % n
			k += 1
		ans = max(ans, longest_run)
	if ans >= n // g:
		print(-1)
	else:
		print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, D, A):
	if 1 not in A:
		return 0
	n = math.gcd(N, D)
	l = N // n
	res = -INF
	for k in range(n):
		L = []
		i = k
		for _ in range(l):
			L.append(A[i])
			i = (i - D) % N
		if 0 not in L:
			return -1
		L2 = L + L
		i1 = -1
		m = -INF
		for i in range(len(L2)):
			if i1 == -1 and L2[i] == 1:
				i1 = i
			elif i1 != -1 and L2[i] == 0:
				m = max(m, i - i1)
				i1 = -1
		res = max(res, m)
	return res
T0 = int(input())
for _ in range(T0):
	(N, D) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(N, D, A))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict, deque
from math import ceil, floor, sqrt, log2, gcd, pi
from heapq import heappush, heappop
from bisect import bisect_left, bisect
from functools import reduce
import sys
abc = 'abcdefghijklmnopqrstuvwxyz'
ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = [-1] * n
	for i in range(n):
		if arr[i] == 0:
			ans[i] = 0
			now = 1
			x = (i + d) % n
			while True:
				if ans[x] > 0 or arr[x] == 0:
					break
				else:
					ans[x] = now
					now += 1
					x = (x + d) % n
	if -1 in ans:
		print(-1)
	else:
		print(max(ans))


import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_left
from bisect import bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq
from collections import deque
import heapq
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	b = list(map(int, input().split()))
	vis = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if not vis[i]:
			c = []
			c.append(b[i])
			vis[i] = 1
			j = (i + n - d) % n
			while j != i:
				vis[j] = 1
				c.append(b[j])
				j = (j + n - d) % n
			k = c + c
			ans1 = 0
			l = len(k)
			i = 0
			j = 0
			while i < l and j < l:
				if k[j] == 0:
					ans1 = max(ans1, j - i)
					i = j + 1
					j = j + 1
				elif k[j] == 1:
					j += 1
			if k.count(1) == l:
				ans = float('inf')
			else:
				ans = max(ans, ans1)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)


Q = int(input())

def main():
	(N, D) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	vis = [False] * N
	task = []
	for i in range(N):
		if vis[i]:
			continue
		tmp = [A[i]]
		vis[i] = True
		j = (i + D) % N
		while j != i:
			tmp.append(A[j])
			vis[j] = True
			j = (j + D) % N
		task.append(tmp)
	for tmp in task:
		n = len(tmp)
		zeros = []
		for i in range(n):
			if tmp[i] == 0:
				zeros.append(i)
		if not zeros:
			print(-1)
			return
		dist = -1
		if len(zeros) == 1:
			dist = max(dist, n - 1)
		else:
			for j in range(len(zeros)):
				dist = max(dist, (zeros[j] - zeros[j - 1] - 1) % n)
		ans = max(ans, dist)
	print(ans)
for _ in range(Q):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = [*map(int, input().split())]
	valid = True
	nullification_cost = 0
	visited = set()
	for start in range(n):
		if start not in visited:
			visited.add(start)
			chain_list = [start]
			while (chain_list[-1] + d) % n != chain_list[0]:
				chain_list.append((chain_list[-1] + d) % n)
				visited.add(chain_list[-1])
			value_list = [a[i] for i in chain_list]
			if sum(value_list) == len(value_list):
				valid = False
				nullification_cost = -1
				break
			else:
				consecutive_ones = 0
				count = 0
				for i in value_list:
					if i == 0:
						count = 0
					else:
						count += 1
						consecutive_ones = max(consecutive_ones, count)
				count = 0
				for i in value_list:
					if i == 0:
						break
					else:
						count += 1
				for i in reversed(value_list):
					if i == 0:
						break
					else:
						count += 1
				consecutive_ones = max(consecutive_ones, count)
				nullification_cost = max(nullification_cost, consecutive_ones)
	if valid:
		print(nullification_cost)
	else:
		print(-1)


import io, os
import math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	ones = []
	for i in range(n):
		if arr[i] == 1:
			ones.append(i)
	if len(ones) == 0:
		print(0)
		return
	visited = [False] * n
	tot = 0
	path = []
	begin = 0
	while begin < n:
		temp = []
		index = begin
		while not visited[index]:
			visited[index] = True
			temp.append(index)
			index = (index + d) % n
		if temp:
			path.append(temp)
		begin += 1
	ans = 0
	for temp in path:
		accu = 0
		temp = temp + temp
		for e in temp:
			if arr[e] == 1:
				accu += 1
			else:
				ans = max(accu, ans)
				accu = 0
		ans = max(ans, accu)
	if ans >= len(path[0]):
		print(-1)
	else:
		print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
import math
import collections
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
r = sys.stdin.readline
for _ in range(int(r())):
	(N, D) = list(map(int, r().split()))
	L = list(map(int, r().split()))
	visited = [0] * N
	if sum(L) == 0:
		print(0)
		continue
	g = math.gcd(N, D)
	flag = 0
	que = collections.deque()
	for i in range(g):
		a = 0
		for j in range(i, N, g):
			a += L[j]
			if L[j] == 0:
				que.append((j, 0))
				visited[j] = 1
		if N // g == a:
			flag = 1
			break
	if flag:
		print(-1)
		continue
	day = 0
	while que:
		(now, p) = que.popleft()
		next = now + D
		if p > day:
			day = p
		if next >= N:
			next -= N
		if visited[next]:
			continue
		visited[next] = 1
		que.append((next, p + 1))
	print(day)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict, deque
from io import BytesIO, IOBase
from itertools import permutations
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def solve_a():
	s = get_str()
	n = len(s)
	if s.count('B') * 2 == n:
		return 'YES'
	return 'NO'

def solve_b():
	n = get_int()
	a = get_ints()
	ans = []
	for i in range(n):
		j = a[i:].index(min(a[i:]))
		if j > 0:
			ans.append((i + 1, i + j + 1, j))
			a = a[:i] + [a[i + j]] + a[i:i + j] + a[i + j + 1:]
	print(len(ans))
	for r in ans:
		print(*r)

def solve_c():
	(n, m, k) = get_ints()
	h = []
	s = set()
	SL = SortedList([])
	chk = set()
	rem = set()
	for i in range(n):
		s = get_str()
		for j in range(m):
			if s[j] == '*':
				chk.add((i, j))
				rem.add((i, j))
	for (i, j) in rem:
		s = 0
		while (i - s, j + s) in rem and (i - s, j - s) in rem:
			s += 1
		s -= 1
		if s >= k:
			for d in range(s + 1):
				chk.discard((i - d, j + d))
				chk.discard((i - d, j - d))
	if len(chk) == 0:
		return 'YES'
	else:
		return 'NO'

def solve_d():
	n = get_int()
	a = get_ints()
	h = []
	talks = []
	for (i, x) in enumerate(a):
		if x > 0:
			heapq.heappush(h, (-x, i + 1))
	while len(h) >= 2:
		(x, i) = heapq.heappop(h)
		(y, j) = heapq.heappop(h)
		x += 1
		y += 1
		talks.append((i, j))
		if x:
			heapq.heappush(h, (x, i))
		if y:
			heapq.heappush(h, (y, j))
	print(len(talks))
	for talk in talks:
		print(*talk)

def solve_e1():
	n = get_int()
	p = get_ints()
	d = deque([])
	for x in p:
		if len(d) == 0 or d[0] < x:
			d.append(x)
		else:
			d.appendleft(x)
	return d

def solve_e2():
	n = get_int()
	a = get_ints()
	SL = SortedList([])
	cnt = 0
	for (i, x) in enumerate(a):
		l = SL.bisect_left(x)
		r = i - SL.bisect_right(x)
		cnt += min(l, r)
		SL.add(x)
	return cnt

def solve_f():
	(n, d) = get_ints()
	g = math.gcd(n, d)
	a = get_ints()
	r = n // g
	m = 0
	for s in range(g):
		c = 0
		tmp = 0
		i = s
		for _ in range(3 * r):
			if a[i] == 1:
				tmp += 1
				c = max(c, tmp)
			else:
				tmp = 0
			i -= d
			i %= n
		if c >= r:
			return -1
		else:
			m = max(m, c)
	return m
t = get_int()
for _ in range(t):
	print(solve_f())


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 8)
import threading

def dfs(i, p, done):
	global cycle
	if done and i == p:
		cycle = True
		return -1
	if a[i] == 0:
		return 0
	if steps[i] != -1:
		return steps[i]
	steps[i] = dfs((i + d) % n, p, True) + 1
	return steps[i]

def answer():
	global cycle
	if sum(a) == 0:
		return 0
	for i in range(n):
		cycle = False
		if a[i] == 1 and steps[i] == -1:
			dfs(i, i, False)
		if cycle:
			return -1
	return max(steps)
(n, d, a, cycle, steps) = (None, None, None, None, None)

def main():
	global n, d, a, cycle, steps
	for T in range(int(input())):
		(n, d) = map(int, input().split())
		a = list(map(int, input().split()))
		cycle = None
		steps = [-1] * n
		print(answer())
threading.stack_size(10 ** 8)
threading.Thread(target=main).start()


import collections
import sys
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt

def ceil(a, b):
	a = -a
	k = a // b
	k = -k
	return k
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def main():
	t = int(input())
	for _ in range(t):
		arr = list(map(int, input().split()))
		n = arr[0]
		d = arr[1]
		arr = list(map(int, input().split()))
		g = gcd(n, d)
		no = n // g
		l = [[] for i in range(g)]
		trig = False
		ma = -1
		for i in range(g):
			j = i
			c = 0
			while c < no:
				if arr[j % n] == 0:
					l[i].append(c)
				c += 1
				j += d
			if l[i] == []:
				trig = True
				break
			if len(l[i]) == 1:
				c -= 1
				ma = max(ma, c)
			else:
				f = l[i][0]
				mad = -1
				prev = l[i][0]
				for j in range(1, len(l[i])):
					mad = max(mad, abs(l[i][j] - prev) - 1)
					prev = l[i][j]
				mad = max(no - (l[i][-1] - l[i][0]) - 1, mad)
				ma = max(ma, mad)
		if trig:
			print(-1)
			continue
		else:
			print(ma)
main()


import sys
import getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_(arr, d):
	n = len(arr)
	sumarr = sum(arr)
	if sumarr == 0:
		return 0
	if sumarr == n:
		return -1
	maxres = 0
	visited = set()
	for (i, x) in enumerate(arr):
		if i in visited:
			continue
		flag = True
		brr = [x]
		cur = i
		nex = (cur + d) % n
		visited.add(cur)
		while nex not in visited:
			cur = nex
			brr.append(arr[cur])
			visited.add(cur)
			nex = (cur + d) % n
		log(brr)
		brr = brr + brr
		curcnt = 0
		for x in brr:
			if x == 0:
				flag = False
				curcnt = 0
			else:
				curcnt += 1
				maxres = max(maxres, curcnt)
		if flag:
			return -1
	return maxres
	return ''
for case_num in range(int(input())):
	(_, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	res = solve(arr, d)
	print(res)


import sys
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return map(int, _r().split())

def rnl():
	return list(rnt())
import collections

def solve(n, d, a):
	(sol, q) = (0, collections.deque([(i, 0) for (i, x) in enumerate(a) if x == 0]))
	while q:
		(i, s) = q.popleft()
		ii = (i + d) % n
		if a[ii] == 1:
			a[ii] = 0
			q.append((ii, s + 1))
		sol = max(sol, s)
	return sol if sum(a) == 0 else -1
for _ in range(rn()):
	(n, d) = rnt()
	a = rnl()
	print(solve(n, d, a))


def getMaxLength(arr, n):
	start = 0
	preCnt = 0
	while start < n and arr[start] == 1:
		preCnt = preCnt + 1
		start = start + 1
	end = n - 1
	suffCnt = 0
	while end >= 0 and arr[end] == 1:
		suffCnt = suffCnt + 1
		end = end - 1
	if start > end:
		return n
	midCnt = 0
	i = start
	result = 0
	while i <= end:
		if arr[i] == 1:
			midCnt = midCnt + 1
			result = max(result, midCnt)
		else:
			midCnt = 0
		i = i + 1
	return max(result, preCnt + suffCnt)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	vis = [0] * n
	i = 0
	m = 0
	f = 1
	while i < n:
		j = i
		new = []
		if vis[i] == 0:
			while vis[j] != 1:
				new.append(a[j])
				vis[j] = 1
				j = (j + k) % n
			if len(new) == new.count(1):
				f = 0
				break
			else:
				m = max(m, getMaxLength(new, len(new)))
		i += 1
	if f == 1:
		print(m)
	else:
		print(-1)


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	s = set()
	for i in range(n):
		if a[(i - d) % n] == 0 and a[i] == 1:
			s.add((i - d) % n)
	ans = 0
	while s:
		ck = set()
		ans += 1
		for i in s:
			j = (i + d) % n
			a[j] = 0
			if a[(j + d) % n] == 1:
				ck.add(j)
		s = ck
	if a.count(1):
		print(-1)
	else:
		print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	(n, d) = inpl()
	a = inpl()
	seen = [0] * n
	res = 0
	for i in range(n):
		if seen[i]:
			continue
		b = [a[i]]
		seen[i] = 1
		while 1:
			j = (i - d) % n
			if seen[j]:
				break
			b.append(a[j])
			seen[j] = 1
			i = j
		ln = len(b)
		if b.count(1) == ln:
			res = -1
			break
		b += list(b)
		ans = 0
		cnt = 0
		for (i, x) in enumerate(b):
			if x:
				cnt += 1
			else:
				ans = max(ans, cnt)
				cnt = 0
		ans = max(ans, cnt)
		res = max(res, ans)
	print(res)


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def solve():
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	v = [0] * n
	ma = 0
	for i in range(n):
		if not v[i]:
			(z, b) = (i, [])
			while not v[z]:
				v[z] = 1
				b.append(z)
				z = (z + d) % n
			(q, l) = (deque(), len(b))
			for j in range(l):
				if not a[b[j]]:
					q.append(j)
			if not len(q):
				return -1
			for j in range(l):
				ma = max((q[0] - j) % l, ma)
				if not a[b[j]]:
					q.append(q.popleft())
	return ma

def main():
	for _ in range(int(input())):
		print(solve())
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	visit = [0] * n
	ans = 0
	for i in range(n):
		if not visit[i]:
			j = i
			x = []
			c = 0
			while not visit[j]:
				visit[j] = 1
				if a[j]:
					c += 1
				elif c:
					x.append(c)
					c = 0
				j += d
				j %= n
			if c:
				x.append(c)
			if a[i] & a[(i - d) % n] and len(x) == 1:
				ans = -1
			elif len(x) == 1:
				ans = max(ans, x[0])
			elif len(x) > 1:
				if a[i] & a[(i - d) % n]:
					ans = max(ans, x[0] + x[-1], max(x))
				else:
					ans = max(ans, max(x))
		if ans == -1:
			break
	print(ans)


import bisect
import collections
import copy
import fractions
import functools
import heapq
import math
import random
import sys

def _p(str):
	sys.stdout.write(str + '\n')

def _i():
	return sys.stdin.readline()

def steps_needed(i, D, A):
	orig_i = i
	visited = set()
	zero_seen = False
	while True:
		if i in visited:
			break
		visited.add(i)
		if A[i] == 0:
			zero_seen = True
			break
		i += D
		i %= len(A)
	if not zero_seen:
		return -1
	i = orig_i
	zeroes_visited = set()
	(steps, max_steps) = (0, 0)
	while True:
		if i in zeroes_visited:
			return max(steps, max_steps)
		if A[i] == 0:
			zeroes_visited.add(i)
			max_steps = max(steps, max_steps)
			steps = 0
		if A[i] == 1:
			steps += 1
		i += D
		i %= len(A)
T = int(_i())
for t in range(T):
	(N, D) = tuple(map(int, _i().split()))
	A = list(map(int, _i().split()))
	GCD = math.gcd(N, D)
	ring_size = N // GCD
	steps_by_ring = [steps_needed(i, D, A) for i in range(GCD)]
	if any((st == -1 for st in steps_by_ring)):
		_p('-1')
	else:
		_p(str(max(steps_by_ring)))
sys.stdout.flush()


import sys
N = int(1000000.0 + 5)
sys.setrecursionlimit(N)

def charming():
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	vis = [0] * n
	res = 0
	for i in range(n):
		if vis[i]:
			continue
		j = i
		b = list()
		ok = False
		while vis[j] == 0:
			if a[j] == 0:
				ok = True
			b.append(a[j])
			vis[j] = True
			j = (j + d) % n
		if ok == False:
			print(-1)
			return
		p = len(b) - 1
		while p >= 0 and b[p] == 1:
			p -= 1
		cnt = len(b) - p - 1
		for i in b:
			if i == 1:
				cnt += 1
				res = max(res, cnt)
			else:
				cnt = 0
	print(res)
for t in range(int(input())):
	charming()


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def shift():
	l2 = [l[(n - d + i) % n] for i in range(n)]
	return l2
for _ in range(inp()):
	(n, d) = invr()
	l = inlt()
	l2 = []
	cnt = 0
	dp = [0 for i in range(n)]
	flag = 1
	for i in range(n):
		v = l[i]
		idx = i
		cnt = 0
		while v and flag:
			if dp[idx]:
				dp[i] = dp[idx] + cnt
				break
			idx2 = (n - d + idx) % n
			if idx2 == i:
				flag = 0
				break
			v = l[idx] & l[idx2]
			if v == 0:
				dp[i] = cnt + 1
				break
			cnt += 1
			idx = (idx - d) % n
	if flag:
		print(max(dp))
	else:
		print(-1)


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
from collections import defaultdict

class UnionFind:

	def __init__(self, N):
		self.parent = dict()
		for i in range(N):
			self.parent[i] = i

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def join(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def time(c):
	if 0 not in c:
		return float('inf')
	c = c + c
	last_0 = None
	ret = 0
	for i in range(len(c)):
		if c[i] == 0:
			last_0 = i
		elif last_0 is not None:
			ret = max(ret, i - last_0)
	return ret

def expand(seed, L, D, N):
	ret = []
	for _ in range(L):
		ret += [seed]
		seed += D
		seed %= N
	return ret

def ans(D, A):
	N = len(A)
	uf = UnionFind(N)
	for i in range(N):
		uf.join(i, (i + D) % N)
	seeds = set()
	for i in range(N):
		seeds.add(uf.find(i))
	class_length = N // len(seeds)
	classes = [expand(seed, class_length, D, N) for seed in seeds]
	classes = [[A[i] for i in c] for c in classes]
	classes = [time(c) for c in classes]
	ret = max(classes)
	if ret == float('inf'):
		ret = -1
	return ret
for _ in range(read_int()):
	(_, D) = read_int_tuple()
	A = read_int_list()
	print(ans(D, A))


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getListGraph():
	return list(map(lambda x: int(x) - 1, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
inf = float('inf')
eps = 10 ** (-10)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
T = getN()
for _ in range(T):
	(N, D) = getNM()
	A = getList()
	logk = 32
	doubling = [[-1] * N for _ in range(logk)]
	for i in range(N):
		if A[i] == 1 and A[(i + D) % N] == 1:
			doubling[0][i] = (i + D) % N
		else:
			doubling[0][i] = -1
	for i in range(1, logk):
		for j in range(N):
			if doubling[i - 1][j] == -1:
				doubling[i][j] = -1
			else:
				doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
	ans = -1
	for i in range(N):
		if A[i] == 0:
			continue
		now = i
		cnt = 0
		for j in range(logk - 1, -1, -1):
			if doubling[j][now] != -1:
				cnt += 1 << j
				now = doubling[j][now]
		ans = max(ans, cnt)
	if ans == 2 ** 32 - 1:
		print(-1)
	else:
		print(ans + 1)


import sys
input = sys.stdin.readline
from math import gcd

def solve(A, n, d):
	g = gcd(n, d)
	ng = n // g
	ans = 0
	for i in range(g):
		B = []
		j = i
		for _ in range(2 * ng):
			B.append(A[j])
			j = (j + d) % n
		r = 0
		cur = 0
		for b in B:
			if b == 1:
				cur += 1
			else:
				cur = 0
			ans = max(ans, cur)
	return ans if ans < ng else -1
T = int(input())
for _ in range(T):
	(n, d) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(A, n, d))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	one = a.count(1)
	if one == n:
		print(-1)
		continue
	if one == 0:
		print(0)
		continue
	mx = 0
	vis = {}
	for i in range(n):
		if a[i] == 1:
			continue
		j = (i + d) % n
		vis[i] = True
		curr = 0
		while True:
			if a[j] == 0:
				break
			vis[j] = True
			j = (j + d) % n
			curr += 1
		mx = max(mx, curr)
	if mx == 0 or len(vis) != n:
		print(-1)
	else:
		print(mx)


import os, sys
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict as dft
from heapq import heappop, heappush
from math import log, sqrt, factorial, cos, tan, sin, radians, log2, ceil, floor, gcd
from bisect import bisect, bisect_left, bisect_right
from decimal import *
import sys, threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline

def modI(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x += m0
	return x
ii = lambda : int(input())
si = lambda : input().rstrip()
mp = lambda : map(int, input().split())
ms = lambda : map(str, input().strip().split(' '))
ml = lambda : list(mp())
mf = lambda : map(float, input().split())
alphs = 'abcdefghijklmnopqrstuvwxyz'

def solve():
	(n, d) = mp()
	ls = ml()
	res = 0
	g = gcd(n, d)
	ng = n // g
	for i in range(g):
		curr = 0
		mx = 0
		st = i
		arr = []
		for j in range(ng):
			arr.append(ls[st])
			st = (st + d) % n
		arr = arr + arr
		for num in arr:
			if not num:
				curr = 0
			else:
				curr += 1
			mx = max(curr, mx)
		if mx == 2 * ng:
			print(-1)
			return
		res = max(res, mx)
	print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=gcd):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
tc = 1
tc = ii()
for i in range(tc):
	solve()


from math import gcd
from itertools import repeat

def line():
	return map(int, input().split())
t = int(input())
for _ in repeat(None, t):
	(n, d) = line()
	a = list(line())
	g = gcd(n, d)
	p = n // g
	e = 0
	for k in range(g):
		l = 0
		for i in range(2 * p):
			v = a[(k + i * d) % n]
			if v:
				l += 1
			else:
				e = max(e, l)
				l = 0
		e = max(e, l)
	if e == 2 * p:
		print(-1)
	else:
		print(e)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	components = []
	visited = [False] * n
	pos = True
	for i in range(n):
		if visited[i]:
			continue
		j = i
		component = []
		while 1:
			if visited[j]:
				break
			visited[j] = True
			component += [a[j]]
			j = (j + k) % n
		components += [component]
		if sum(component) == len(component):
			pos = False
			break
	if not pos:
		print(-1)
		continue
	ans = 0
	for component in components:
		a = component + component
		cur = 0
		for x in a:
			if x == 1:
				cur += 1
			else:
				cur = 0
			ans = max(ans, cur)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, d) = map(int, input().split())
	A = list(map(int, input().split()))
	ANS = [-1] * n
	for i in range(n):
		if A[i] == 0:
			ANS[i] = 0
			x = (i + d) % n
			now = 1
			while True:
				if ANS[x] > 0 or A[x] == 0:
					break
				else:
					ANS[x] = now
					now += 1
					x = (x + d) % n
	if -1 in ANS:
		print(-1)
	else:
		print(max(ANS))