# Bulbs and Wires SOLUTIONS BULBS

Page Contents

### Bulbs and Wires SOLUTIONS BULBS

There are N lights straight, numbered 1 through N from left to right. Every bulb can be in one of the states “on” or “off”. At first, all the bulbs are “off”. Every bulb is likewise associated with its (at generally two) neighboring bulbs by wires.

You should arrive at a state depicted by a given a parallel string S with length N ― for each legitimate I, if the I-th character of S is ‘1’, the I-th bulb ought to be “on”, and in the event that it is ‘0’, the I-th bulb ought to be “off”. You may do that by playing out the accompanying strides in the provided request:

Slice up to K of the N−1 wires between contiguous bulbs (potentially none of them).

Switch on certain bulbs (perhaps none). Here, at whatever point two bulbs are as yet associated by wires (straightforwardly or in a roundabout way) and one of them gets turned on, at that point the other one additionally gets turned on.

Detach a few bulbs from the electrical organization. Here, detaching a bulb turns it off, yet it doesn’t influence some other bulbs ― if a bulb was turned on before this progression and it was not separated in this progression, it remains turned on thereafter.

Limit the quantity of bulbs you have to separate in sync 3 so as to arrive at the given last condition of the bulbs.

Information

The principal line of the information contains a solitary number T signifying the quantity of experiments. The portrayal of T experiments follows.

The primary line of each experiment contains two space-isolated numbers N and K.

The subsequent line contains a solitary string S.

Yield

For each experiment, print a solitary line containing one whole number ― the most modest number of bulbs you have to detach.

Requirements

1≤T≤1,000

0≤K<N≤105

|S|=N

S contains just characters ‘0’ and ‘1’

the whole of N over all experiments doesn’t surpass 5⋅105

Model Input

5 2

01001

Model Output

Clarification

Model case 1: We can cut the wires between sets of bulbs (2,3) and (4,5), switch on bulbs 1, 2 and 5, and afterward detach bulb 1.

Related: