Giải bài trực tuyến

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⁵; 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⁵.

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