Có một chú ếch đang ở trên trục \(Ox\) tại toạ độ \(1\), và bây giờ chú muốn di chuyển đến toạ độ \(n\).
Biết rằng, tại mỗi bước di chuyển, chú có thể nhảy từ vị trí \(x\) đến vị trí \(x+a\), với điều kiện \(a\) là một số nguyên và \(1\le a\le d\), trong đó \(d\) là một số nguyên cho trước.

Biết rằng, các toạ độ trên trục \(Ox\) có một vài toạ độ có hoa sen, và chú ếch chỉ có thể di chuyển từ hoa sen này sang hoa sen khác mà thôi (các toạ độ \(1\) và toạ độ \(n\) luôn có hoa sen)

Nhiệm vụ của bạn là hãy tính toán xem, chú ếch cần ít nhất bao nhiêu lần nhảy để có thể di chuyển đến toạ độ \(n\), biết rằng ban đầu chú ếch ở toạ độ \(1\).

Nếu chú ếch không thể di chuyển đến toạ độ \(n\), thì in ra \(-1\)

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
• ++ Dòng đầu tiên chứa hai số nguyên \(n\) và \(d(2\le n\le 100,1\le d\le n-1)\)
• ++ Dòng thứ hai chứa xâu nhị phân \(s\) có độ dài là \(n\), trong đó số \(1\) thể hiện toạ độ có hoa sen và số \(0\) thể hiện toạ độ không có hoa sen.

Output

• Ứng với mỗi testcase, hãy in kết quả ra màn hình.

Example

2
8 4
10010101
4 2
1001

2
-1