SOLVE

LATER

Help Sachin Dev Sahoo

/

Sachin Dev Sahoo is a top coder from NSIT.It is evident from his high ratings on CF and Codechef as well :p. He always takes his laptop with him wherever he goes. One day (while on a trek trip ) a monster challenged him to solve one easy task else he was going to kill him. The task goes as follows : - He was given a string consisting of 1's and 0's.Now the task is to make the string consisting of only 1's.But he is allowed to perform only the following operation- Take exactly k consecutive elements of string and change 1 to 0 and 0 to 1 i.e apply not(!) operation on each element.

Each operation takes 1 sec so he has to tell the minimum time required to make the string of 1's only. If not possible print -1.Help Sachin in this task.

**Input**

The first line of the input gives the number of test cases, T. T test cases follow.Each consists of one line with a string **S** and an integer **K**. **S** represents string of 1's and 0's.**K** represent the number of consecutive elements which can be changed.

**Output**

For each test case, output one line containing the answer i.e the minimum time to make the string of 1's only and -1 if not possible.

**Constraints**

1 ≤ T ≤ 100. 2 ≤ K ≤ length of S.

30 points: 2 ≤ length of S ≤ 10.

70 points: 2 ≤ length of S ≤ 1000.

Explanation

In 1 testcase- You can get 1 by first changing the leftmost 3 elements, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 left out 0's to 11111111; In 3 sec.

In 2 testcase- String consist of only 1's so no change needed.

In 3 testcase- There is no way to make the string of only 1's so -1.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...