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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from sys import setrecursionlimit\r\nsetrecursionlimit(10 * 9)\r\n\r\ndef solve(i):\r\n    if i + k >= n:\r\n        return 1\r\n\r\n    if i in dp:\r\n        return dp[i]\r\n\r\n    mini = float('inf')\r\n    for j in range(i+1, min(n, i+k+1)):\r\n        if i == -1 or a[i] == a[j]:\r\n            mini = min(mini, solve(j) + 1)\r\n\r\n    dp[i] = mini\r\n    return dp[i]\r\n\r\n\r\nfor _ in range(int(input())):\r\n    n, k = map(int, input().split())\r\n    a = list(map(lambda x: int(x) % 2, input().split()))\r\n\r\n    le = lo = -1\r\n    se = so = -1\r\n\r\n    for i in range(n-k, n):\r\n        if a[i] == 0:\r\n            le = i\r\n            break\r\n\r\n    for i in range(n-k, n):\r\n        if a[i] == 1:\r\n            lo = i\r\n            break\r\n\r\n    m1 = float('inf')\r\n    if le != -1:\r\n        m1 = 0\r\n        while True:\r\n            lle = -1\r\n\r\n            for i in range(se + 1, se + k + 1):\r\n                if i == le:\r\n                    m1 += 2\r\n                    break\r\n\r\n                if a[i] == 0:\r\n                    lle = i\r\n\r\n            else:\r\n                if lle == -1:\r\n                    m1 = float('inf')\r\n                    break\r\n\r\n                se = lle\r\n                m1 += 1\r\n                continue\r\n\r\n            break\r\n\r\n    m2 = float('inf')\r\n    if lo != -1:\r\n        m2 = 0\r\n        while True:\r\n            llo = -1\r\n\r\n            for i in range(so + 1, so + k + 1):\r\n                if i == lo:\r\n                    m2 += 2\r\n                    break\r\n\r\n                if a[i] == 1:\r\n                    llo = i\r\n\r\n            else:\r\n                if llo == -1:\r\n                    m2 = float('inf')\r\n                    break\r\n\r\n                so = llo\r\n                m2 += 1\r\n                continue\r\n\r\n            break\r\n\r\n    if min(m1, m2) != float('inf'):\r\n        print(min(m1, m2))\r\n    else:\r\n        print(-1)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13845