9597: Field of Fire

Alarm! Fire is taking over the forest!

The shape of this forest is like a ring and can be divided into $n$ parts. Part $i(1\le i\le n)$ is adjacent only to Part $((i-2)\mathrm{m}\mathrm{o}\mathrm{d}n)+1$ and Part $(i\mathrm{m}\mathrm{o}\mathrm{d}n)+1$. If no action is taken and there is a fire in Part $i$, its adjacent parts will also be engulfed by flames in one minute.

As a responsible resident yourself, you have called the firefighters to come as soon as possible to put out this scary fire. However, it will take t₀ minutes before they can ever get here. Is there anything you could do?

There is! You decide to set a controllable fire by yourself on exactly one part of the forest to get a fire isolation zone immediately before the fire can ever get to it. In that way, the fire can never spread over this place afterwards.

But it's hard to make a wise decision: You need to choose the place of the fire isolation zone to guarantee more parts of the forest remain unburned. What is the maximum number of unburned parts you can get before firefighters come?

Each test contains multiple test cases. The first line contains the number of test cases T (1≤T≤10⁴) .
Each test case consists of $2$ lines.
The first line contains two integers n,t₀ (1≤n,t₀≤10⁵), the number of parts in the forest and the time firefighters need to get to the forest.
The second line contains a string $(|s|=n)$ consisting of $0$ and $1$. The part $i$ is currently on fire if and only if s_i=1. It is guaranteed that there exists one $i(1\le i\le n)$ such that s_i=1.
It is guaranteed that ∑n over all test cases in one test will not exceed 5×10⁵.

For each test case, output one integer:  the maximum number of unburned parts in the forest when the firefighters come.

For the first test case, once you burn Part $2$, the fire only gets time to burn Part $4$ and $5$, leaving Part $3$ unburned.