Binary String Extraction from Patterned Sequences

bj12z_jiasiyuan constructed \(n+1\) infinite binary sequences defined as follows:

• The 1^st sequence is \(1111111\dots\) (i.e. starts with 1 and the gap between adjacent 1's is 0).
• The 2^nd sequence is \(10101010\dots\) (i.e. starts with 1 and the gap between adjacent 1's is 1).
• The 3^rd sequence is \(100100100\dots\) (i.e. starts with 1 and the gap between adjacent 1's is 2).
• \(\vdots\)
• The \((n+1)\)^th sequence starts with 1 and the gap between adjacent 1's is \(n\).

For a fixed gap \(d\), the corresponding infinite sequence is defined by placing a '1' at index \(0\) and then every \(d+1\) position. In other words, the sequence is defined by:

[ a_i = \begin{cases} 1, & \text{if } (i + r) \equiv 0 ; (\bmod; d+1) \ 0, & \text{otherwise}, \end{cases} ]

where \(r\) is some offset (since the contiguous segment may be extracted starting from any index) and \(0 \le d \le n\).

You are given \(T\) queries. Each query consists of three inputs \(n, m\) and a binary string \(s\) of length \(m\). For each query, determine if \(s\) can be obtained as a contiguous substring from one of the \(n+1\) sequences described above.

If it is possible for some choice of gap \(d\) (with \(0 \le d \le n\)) and some offset \(r\), print YES; otherwise, print NO.

inputFormat

The first line contains a single integer \(T\) denoting the number of queries.

Each of the following queries consists of two lines:

• The first line contains two integers \(n\) and \(m\), where \(n\) is the maximum gap and \(m\) is the length of the binary string.
• The second line contains a binary string \(s\) of length \(m\).

outputFormat

For each query, output YES if the binary string can be extracted from one of the sequences; otherwise, output NO.

sample

4
2 3
101
1 3
010
2 4
0010
1 2
00

YES
YES
YES
NO