Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VPBINDEG - VPBINDEG

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 ≤ N ≤ 105; 1 ≤ k*2 ≤ 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á 105.

Output

Dòng 1…T: dòng i ghi số nguyên kết quả của test i. 

Example

Input:

1

3 1

011 

Output: 2

Được gửi lên bởi:Thương
Ngày:2014-11-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC MAWK BC C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PS PROLOG R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc năm 2014-2015

hide comments
2017-05-01 11:45:56
Oh men, 1 đút AC =))
2016-10-01 07:14:52 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/359/vpbindeg-spoj/
2014-11-01 14:08:00 comments
xâu con có cần liên tiếp ko bạn PS??

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.