VPBINDEG

View as PDF

Submit solution

Points: 1.21 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc nãm 2014-2015
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

Please read the guidelines before commenting.


There are no comments at the moment.