Statement
我有一个由 N 个二进制数字组成的序列。我正在寻找一个 0 和 1 的比例恰好合适的子串，但它可能不存在，所以我会退而求其次，找一个相当好的。
你能找到一个子串，其中 1 所占的比例尽可能接近给定的比例 F 吗？输出这样的子串开始的最早可能索引。
Input
输入的第一行给出测试用例的数量 T。接下来是 T 个测试用例。每个测试用例以一行开始，包含 N 和 F。F 是一个介于 0 和 1 之间（含）的小数，小数点后恰好有 6 位数字。下一行包含 N 个数字，每个数字是 0 或 1。
### 数据范围
- 1 ≤ T ≤ 100。
- 0 ≤ F ≤ 1
- F 小数点后恰好有 6 位数字。
- 1 ≤ N ≤ 1000。
- 1 ≤ N ≤ 500,000。
Output
按测试用例顺序逐个输出答案。对于每个测试用例，输出一行，包含 y，其中 y 是 1 所占比例尽可能接近 F 的子串起始位置的 0 基索引。如果有多个可能的答案，输出最小的正确值。
Examples
Input
5
12 0.666667
001001010111
11 0.400000
10000100011
9 0.000000
111110111
5 1.000000
00000
15 0.333333
000000000011000Output
5
5
5
0
6Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: binary-search
- Tag: math
- Tag: prefix-sum