There are $N$ cells numbered 1,2,….., N, and every cell has some positive value. you will be given an array $A_1$,$A_2$,…,$A_N$ where $A_i$ is the value of $ith$ cell and an integer $K$.
There is a monkey who wants to reach the $right$ side of the last ($Nth$) cell, initially, the monkey was left side of the first ($1st$) cell. 
In the first step, he can jump into any cell numbered 1,2,….., K.Once he jumped into any cell $i$ next he can only jump to the cell $j$ such that-
- j>i
- j-i <= K  
- A[i]%2 == A[j]%2
You have to find out what is the minimum number of steps required to reach the right side of the cell or In case it's not possible to reach the right side of the cell your answer should be $-1$.NOTE: As soon as monkey reach any cell whose distance from the last cell is less than K, then in the last step, he will jump out to the right side of the ($Nth$) cell.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1$,$A_2$,…,$A_N$

-----Output:-----
For each test case, output in a single line minimum steps or $-1$.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 2*10^5$
- $1 \leq K \leq N$
- $0 \leq A_i \leq 10^6$
- $\text{the sum of N over all test cases does not exceed $5*10^{5}$}$

-----Sample Input:-----
1
2 2
3 4

-----Sample Output:-----
2 

-----EXPLANATION:-----
in the first step, you can jump into any cell 1 or 2 and then in the second step you will jump 
out to the right side of 2nd cell
remember we don't want to reach $Nth$ cell we want to reach the right side of the nth cell.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import setrecursionlimit
setrecursionlimit(10 * 9)

def solve(i):
	if i + k >= n:
		return 1
	if i in dp:
		return dp[i]
	mini = float('inf')
	for j in range(i + 1, min(n, i + k + 1)):
		if i == -1 or a[i] == a[j]:
			mini = min(mini, solve(j) + 1)
	dp[i] = mini
	return dp[i]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(lambda x: int(x) % 2, input().split()))
	le = lo = -1
	se = so = -1
	for i in range(n - k, n):
		if a[i] == 0:
			le = i
			break
	for i in range(n - k, n):
		if a[i] == 1:
			lo = i
			break
	m1 = float('inf')
	if le != -1:
		m1 = 0
		while True:
			lle = -1
			for i in range(se + 1, se + k + 1):
				if i == le:
					m1 += 2
					break
				if a[i] == 0:
					lle = i
			else:
				if lle == -1:
					m1 = float('inf')
					break
				se = lle
				m1 += 1
				continue
			break
	m2 = float('inf')
	if lo != -1:
		m2 = 0
		while True:
			llo = -1
			for i in range(so + 1, so + k + 1):
				if i == lo:
					m2 += 2
					break
				if a[i] == 1:
					llo = i
			else:
				if llo == -1:
					m2 = float('inf')
					break
				so = llo
				m2 += 1
				continue
			break
	if min(m1, m2) != float('inf'):
		print(min(m1, m2))
	else:
		print(-1)


def f(c):
	t = s + c
	i = 0
	r = 1
	while i < len(t):
		j = t.rfind(c, i, i + k)
		if j < 0:
			return n
		r += 1
		i = j + 1
	return r
R = lambda : list(map(int, input().split()))
(t,) = R()
for _ in range(t):
	(n, k) = R()
	n += 3
	s = ''.join((f'{x % 2}' for x in R()))
	print(min(list(map(f, '01'))) % n - 1)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	if k > n:
		print(1)
		continue
	curr = -1
	i = 0
	temp_even_place = -1
	ans_of_even = 0
	while curr + k < n:
		while i - curr <= k:
			if A[i] % 2 == 0:
				temp_even_place = i
			i += 1
		if temp_even_place == curr:
			ans_of_even = -1
			break
		else:
			ans_of_even += 1
			curr = temp_even_place
	if ans_of_even != -1:
		ans_of_even += 1
	curr = -1
	i = 0
	temp_odd_place = -1
	ans_of_odd = 0
	while curr + k < n:
		while i - curr <= k:
			if A[i] % 2 == 1:
				temp_odd_place = i
			i += 1
		if temp_odd_place == curr:
			ans_of_odd = -1
			break
		else:
			ans_of_odd += 1
			curr = temp_odd_place
	if ans_of_odd != -1:
		ans_of_odd += 1
	if ans_of_even == -1 and ans_of_odd == -1:
		print(-1)
	elif ans_of_odd == -1 and ans_of_even != -1:
		print(ans_of_even)
	elif ans_of_odd != -1 and ans_of_even == -1:
		print(ans_of_odd)
	elif ans_of_odd != -1 and ans_of_even != -1:
		print(min(ans_of_even, ans_of_odd))


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7
T = int(stdin.readline())
for _ in range(T):
	(n, k) = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	p = [[0]]
	p.append([0])
	for i in range(n):
		p[a[i] % 2].append(i + 1)
	p[0].append(n + 1)
	p[1].append(n + 1)
	res = [True, True]
	for j in range(2):
		for i in range(len(p[j]) - 1):
			if p[j][i + 1] - p[j][i] > k:
				res[j] = False
				break
	mn = 500000
	for j in range(2):
		if not res[j]:
			continue
		i = 1
		s = 0
		m = 0
		while i < len(p[j]):
			if p[j][i] - s > k:
				s = p[j][i - 1]
				m += 1
			else:
				i += 1
		m += 1
		mn = min(mn, m)
	if mn == 500000:
		print(-1)
	else:
		print(mn)