我有一个包含 $N$ 个二进制数字的序列。我正在寻找一个 0 和 1 比例恰好符合要求的子串，但它可能并不存在，所以我退而求其次，寻找一个尽可能接近要求的子串。

请你找出一个子串，使得其中 1 的比例尽可能接近给定的分数 $F$。输出该子串起始位置的最小下标。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $N$ 和 $F$。$F$ 是一个介于 0 到 1 之间（含 0 和 1）的十进制分数，小数点后恰好有 6 位数字。下一行包含 $N$ 个数字，每个数字均为 0 或 1。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 1 的比例最接近 $F$ 的子串的起始下标（从 0 开始计数）。如果存在多个可能的答案，输出最小的下标值。

数据范围

$1 \le T \le 100$。

$0 \le F \le 1$。

$F$ 小数点后恰好有 6 位数字。

小数据（5 分）

$1 \le N \le 1000$。

大数据（22 分）

$1 \le N \le 500,000$。

样例

输入 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

说明

在 Case #1 中，不存在 1 的比例恰好为 $666667/1000000$ 的子串。最接近的比例是 $2/3$。输入字符串中有 5 个子串达到了这个比例——3 个长度为 3 的子串，起始下标分别为 5、7 和 8（分别为 101、101 和 011）；以及 2 个长度为 6 的子串，起始下标分别为 5 和 6（分别为 101011 和 010111）。这些下标中最小的是 5。