Please help me solve this problem

help
1

Kabaddi Modified

Arnab has made a team and he wants to fight with another team with some modified form of Kabaddi. In this game, all the players stand in a line. Now in a turn Arnab’s team member can hold and win over an player of opposite team upto KK distance apart. Each player of Arnab’s team can win over only one opponent player and upto KK distance. Player of Arnab’s team is marked by 11 and opponents team is marked by 00. Find the maximum number of people Arnab’s team can win over.

Input format

The first line contains an integer TT, denoting the number of test cases. Each test case contains a string SS of 00 and 11 and another integer KK.

Output format

For every testcase on a line print the maximum number of wins.

Constraints:

1<=T<=101<=T<=10 1<=|S|<=10001<=|S|<=1000 1<=K<=1001<=K<=100

Example

Input

1 101001 3

Output

3

Explanation

First player can win over 2nd2nd player, 3rd3rd player can win over 4th4th player and last player can win over 2nd2nd last player.

2

You need to share a link to the problem so it can be verified that this problem is not from a ongoing contest.

3

actually this problem is from my interview preparation course

i dont think you will be able to see it

4

Maybe you should try asking the instructor or on Prepbytes Forum. It is unlikely you will receive a complete solution for a coding assignment here.

5

ya i was into that but was not getting.

6