A bitstring is a string consisting only of the characters 0 and 1. A bitstring is called k-balanced if every substring of size k of this bitstring has an equal amount of 0 and 1 characters (k/2 of each).

You are given an integer k and a string s which is composed only of characters 0, 1, and ?. You need to determine whether you can make a k-balanced bitstring by replacing every ? characters in s with either 0 or 1.

A string a is a substring of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). Description of the test cases follows.

The first line of each test case contains two integers n and k (2 ≤ k ≤ n ≤ 3 ⋅ 10^5, k is even) — the length of the string and the parameter for a balanced bitstring.

The next line contains the string s (|s| = n). It is given that s consists of only 0, 1, and ?.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print YES if we can replace every ? in s with 0 or 1 such that the resulting bitstring is k-balanced, or NO if it is not possible.

Example

Input


9
6 4
100110
3 2
1?1
3 2
1?0
4 4
????
7 4
1?0??1?
10 10
11??11??11
4 2
1??1
4 4
?0?0
6 2
????00


Output


YES
YES
NO
YES
YES
NO
NO
YES
NO

Note

For the first test case, the string is already a 4-balanced bitstring.

For the second test case, the string can be transformed into 101.

For the fourth test case, the string can be transformed into 0110.

For the fifth test case, the string can be transformed into 1100110.
from math import ceil
from collections import Counter
#from collections import defaultdict
#from collections import deque
# from bisect import bisect_left as bl, bisect_right as br
# from itertools import accumulate,permutations as perm,combinations as comb
# import heapq
# from fractions import Fraction
"""author-bravotango. FastIO code by pajanegod"""
import sys


def main():
    t = Iint()
    for _ in range(t):
        n, k = Imap()
        s = Istr()
        if k == n:
            sc = Counter(s)
            if sc['0'] < sc['1'] and sc['0']+sc['?'] < sc['1']:
                print("NO")
                continue
            elif sc['0'] > sc['1'] and sc['1']+sc['?'] < sc['0']:
                print("NO")
                continue
            else:
                print("YES")
                continue
        substring_count = ceil(n/k)
        box = [-1]*k
        for j in range(substring_count):
            start = k*j
            debug(start)
            length = min(k, n-start)
            for i in range(length):
                b1 = box[i]
                bw = s[start+i]
                if b1 == -1:
                    box[i] = bw
                elif b1 == '?':
                    box[i] = bw
                elif b1 == bw:
                    continue
                elif b1 == '0' and bw == '1':
                    break
                elif b1 == '1' and bw == '0':
                    break
            else:
                continue
            break
        else:
            sc = Counter(box)
            if sc['0'] < sc['1'] and sc['0']+sc['?'] < sc['1']:
                print("NO")
                continue
            elif sc['0'] > sc['1'] and sc['1']+sc['?'] < sc['0']:
                print("NO")
                continue
            else:
                print("YES")
                continue
        print("NO")


en = enumerate
# IO region1


def debug(*args, c=6): pass  # print('\033[3{}m'.format(c), *args, '\033[0m', file=sys.stderr)


FIO = 10


BUFSIZE = 8*1024


def Istr(): return input()


def Iint(): return int(input())


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


def Imap(): return map(int, input().split())   # int map


def Plist(li, s=' '): print(s.join(map(str, li)))   # non string iterable


if not FIO:
    if __name__ == '__main__':
        main()
        exit()
else:
    from io import BytesIO, IOBase
    import os
# FastIO


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)


def input(): return sys.stdin.readline().rstrip("\r\n")

# /IO region


if __name__ == '__main__':
    main()
