VPBINDEG - VPBINDEG

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 ≤ 10 5 ; 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á 10 5 .

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

  • Người up: only_love97
  • Nguồn bài: Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc nãm 2014-2015