P13235 [GCJ 2015 Finals] Pretty Good Proportion

I have a sequence of $\mathbf{N}$ binary digits. I am looking for a substring with just the right proportion of 0s and 1s, but it may not exist, so I will settle for something that's just pretty good. Can you find a substring where the fraction of 1s is as close as possible to the given fraction $\mathbf{F}$? Output the earliest possible index at which such a substring starts.

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each one starts with a line containing $\mathbf{N}$ and $\mathbf{F}$. $\mathbf{F}$ will be a decimal fraction between 0 and 1 inclusive, with exactly 6 digits after the decimal point. The next line contains $\mathbf{N}$ digits, each being either 0 or 1.

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the 0-based index of the start of the substring with the fraction of 1s that is as close as possible to $\mathbf{F}$. If there are multiple possible answers, output the smallest correct value.

**Sample Explanation** In Case #1, there is no substring that has exactly a $1$-proportion of exactly $666667/1000000$. The closest we can get is $2/3$. The input string has 5 substrings that achieve it -- $3$ substrings of length 3 that start at indices $5, 7,$ and $8$ ($101, 101,$ and $011$); as well as two substrings of length $6$ that start at indices $5$ and $6$ ($101011$ and $010111$). The smallest of these indices is $5$. **Limits** - $1 \leq \mathbf{T} \leq 100$. - $0 \leq \mathbf{F} \leq 1$ - $\mathbf{F}$ will have exactly 6 digits after the decimal point. **Small dataset** - Time limit: ~~240~~ 5 seconds. - $1 \leq \mathbf{N} \leq 1000$. **Large dataset** - Time limit: ~~480~~ 10 seconds. - $1 \leq \mathbf{N} \leq 500,000$.