Pretty Good Proportion (Large)

You have a string of $N$ binary digits. You want a substring whose proportion of 1s is exactly some target value, but such a substring may not exist, so a close one will do.

Given a decimal fraction $F$, find a substring whose proportion of 1s is as close to $F$ as possible. The proportion of 1s of a substring is the number of 1s in it divided by its length. A substring is a run of consecutive characters and its length is at least 1. Report the smallest starting position among the substrings that come closest.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case begins with a line containing $N$ and $F$, separated by one space. $F$ is a decimal fraction between 0 and 1 inclusive, written with exactly 6 digits after the decimal point. The next line contains $N$ digits, each 0 or 1, with no spaces.

Limits

• $1 \le T \le 100$
• $0 \le F \le 1$
• $F$ has exactly 6 digits after the decimal point
• $1 \le N \le 500000$

For each test case, print one line of the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the starting position of a substring whose proportion of 1s is as close to $F$ as possible. Positions are counted from 0. When several starting positions are possible, print the smallest one.

Take $F = 0.666667$ and the string 001001010111. No substring has a proportion of 1s equal to $666667/1000000$, and the closest reachable value is $2/3$. Five substrings reach it: 101, 101, 011 of length 3 starting at positions 5, 7, 8, and 101011, 010111 of length 6 starting at positions 5 and 6. The smallest of those starting positions is 5.