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