Submit solution
Points:
1.21 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Một xâu nhị phân được gọi là bậc ~k~ nếu nó bắt đầu bằng ~0~, kết thúc bằng ~1~ và chứa một xâu con không phải tiền tố hay hậu tố có bậc ~k−1~, đồng thời ~k~ là số nguyên lớn nhất thỏa mãn tính chất đó. Xâu rỗng được hiểu là có bậc ~0~.
Cho xâu nhị phân ~S~ độ dài ~N~, xác định số xâu con bậc ~k~ của ~S~.
Input
- Dòng ~1~: số nguyên ~T~ là số test. Mỗi test được cho trên hai dòng:
- Dòng ~1~: hai số nguyên ~N~, ~k~ ~(2 \leq N \leq 10^{5}~; ~1 \leq k \times 2 \leq N)~
- Dòng ~2~: xâu nhị phân ~S~ độ dài ~N~.
Tổng độ dài xâu của các test không vượt quá ~10^{5}~.
Output
- Dòng ~1~ ...~T~: dòng ~i~ ghi số nguyên kết quả của test ~i~.
Sample Input
1
3 1
011
Sample Output
2
Comments