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: interview

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)


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 += 2
  s = ''.join(f'{x%2}' for x in R())
  print(min(list(map(f, '01'))) % n - 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)


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(f(c) for c in '01') % n - 1)


def f(s):
  i = 0
  r = 1
  while i < len(s):
    j = s.rfind(s[-1], 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(f(s + c) for c in '01') % n - 1)


# cook your dish here
#2

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
    #even 
    curr = -1
    i = 0
    temp_even_place = -1
    ans_of_even = 0
    while curr + k < n: #need to find a stop 
        while i-curr <= k:
            if A[i]%2 == 0:
                temp_even_place = i
            i+=1
        if temp_even_place == curr: #no new stop found
            ans_of_even = -1
            break
        else:
            ans_of_even += 1
            curr = temp_even_place
    if ans_of_even != -1:
        ans_of_even += 1

    #odd 
    curr = -1
    i = 0
    temp_odd_place = -1
    ans_of_odd = 0
    while curr + k < n: #need to find a stop 
        while i-curr <= k:
            if A[i]%2 == 1:
                temp_odd_place = i
            i+=1
        if temp_odd_place == curr: #no new stop found
            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
# sys.stdin = open('input.txt', 'r') 
# sys.stdout = open('output.txt', 'w')
 
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())
# T = 1

for _ in range(T):
    # n = int(stdin.readline())
    n,k = list(map(int,stdin.readline().split()))
    a = list(map(int,stdin.readline().split()))
    # w = list(map(int,stdin.readline().split()))
    # q = list(map(int,stdin.readline().split()))
    # b = list(map(int,stdin.readline().split()))
    # s = stdin.readline().strip('\n')
    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)

import sys
# sys.stdin = open('input.txt', 'r') 
# sys.stdout = open('output.txt', 'w')
 
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())
# T = 1

for _ in range(T):
    # n = int(stdin.readline())
    n,k = list(map(int,stdin.readline().split()))
    a = list(map(int,stdin.readline().split()))
    # w = list(map(int,stdin.readline().split()))
    # q = list(map(int,stdin.readline().split()))
    # b = list(map(int,stdin.readline().split()))
    # s = stdin.readline().strip('\n')
    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)