Pretty Good Proportion (Small)

You have a string of $N$ binary digits. Find a contiguous substring whose fraction of 1s is as close as possible to a target value $F$. A substring whose fraction equals $F$ exactly may not exist, so take the one with the smallest difference.

The fraction of 1s in a substring is the number of 1s in it divided by its length. Only substrings of length 1 or more count. Report the starting index of a substring that minimizes $|\text{fraction} - F|$.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains $N$ and $F$, separated by a single space. $F$ is a decimal fraction between 0 and 1 inclusive with exactly 6 digits after the decimal point. The second line contains $N$ digits, each 0 or 1, with no separators.

Limits

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

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the starting index of the substring whose fraction of 1s is closest to $F$. Indices are 0-based. If several substrings achieve the smallest error, print the smallest starting index among them.

Take the string 001001010111 with $F = 0.666667$. No substring has a fraction of 1s equal to $666667/1000000$. The closest reachable value is $2/3$, and five substrings reach it. The ones of length 3 start at indices 5, 7, and 8 (101, 101, 011), and the ones of length 6 start at indices 5 and 6 (101011, 010111). The smallest of those starting indices is 5.