#213352. [GCJ 2015 Finals] Pretty Good Proportion

I have a sequence of 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 ? Output the earliest possible index at which such a substring starts.

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

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

样例输入 1

5
12 0.666667
001001010111
11 0.400000
10000100011
9 0.000000
111110111
5 1.000000
00000
15 0.333333
000000000011000

样例输出 1

Case #1: 5
Case #2: 5
Case #3: 5
Case #4: 0
Case #5: 6

Sample Explanation

In Case #1, there is no substring that has exactly a -proportion of exactly . The closest we can get is . The input string has 5 substrings that achieve it -- substrings of length 3 that start at indices and ( and ); as well as two substrings of length that start at indices and ( and ). The smallest of these indices is .

Limits

• .
• will have exactly 6 digits after the decimal point.

Small dataset

• Time limit: 240 5 seconds.
• .

Large dataset

• Time limit: 480 10 seconds.
• .