All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Help Sachin Dev Sahoo
Tag(s):

Easy

Problem
Editorial
Analytics

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.

SAMPLE INPUT
3
00010110 3
11111 4
01010 4
SAMPLE OUTPUT
3
0
-1
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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?