### 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.