Question
Access Control
Yash is a visitor in NewtonSchool's new office. All doors inside the office require a swipe of access card.
The access card allows a fixed number of swipes and expires after that. You are given a binary string S of length N and an integer X. Let Si = 0 denote the swipe of access card, thus reducing the remaining swipes by 1; and Si = 1 denote a renewal of access card which sets the remaining swipes to X.
Find whether the string S denotes a valid string of renewal and swipes where the card never expires before a door is accessed. Note that the access card has 0 swipes left in the beginning.
Input
The first line of the input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers N and X - the length of the binary string and the number of swipes left in the access card after renewal.
The next line contains a binary string S of length N.
Constraints
1 ≤ T ≤ 105
1 ≤ X ≤ N ≤ 105
Si ∈ {0, 1}
Note: Sum of N over all test cases won't exceed 2x105
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers N and X - the length of the binary string and the number of swipes left in the access card after renewal.
The next line contains a binary string S of length N.
Constraints
1 ≤ T ≤ 105
1 ≤ X ≤ N ≤ 105
Si ∈ {0, 1}
Note: Sum of N over all test cases won't exceed 2x105
Output
For each test case, output on a new line, Yes, if the string S denotes a valid string of renewal and swipes where the card never expires before a door is accessed. Otherwise output No.
Example
Sample Input
2
4 4
0111
4 2
1001
Sample Output
No
Yes
Explanation
Test Case 1: Initially card has 0 swipes. Thus, Yash would not be able to access the first door.
Test Case 2: Yash renews the card and thus gets 2 swipes. Thus, Yash would be able to access the next two doors. At the end, Yash renews the card again and is left with 2 swipes.
2
4 4
0111
4 2
1001
Sample Output
No
Yes
Explanation
Test Case 1: Initially card has 0 swipes. Thus, Yash would not be able to access the first door.
Test Case 2: Yash renews the card and thus gets 2 swipes. Thus, Yash would be able to access the next two doors. At the end, Yash renews the card again and is left with 2 swipes.