적당히 좋은 비율 (큰 입력)

$N$개의 이진 숫자로 이루어진 문자열이 하나 있다. 1의 비율이 원하는 값과 정확히 같은 부분 문자열을 찾고 싶지만 그런 부분 문자열이 없을 수도 있으니, 가장 가까운 것으로 만족하려고 한다.

소수 $F$가 주어질 때, 1의 비율이 $F$에 가장 가까운 부분 문자열을 찾아라. 부분 문자열의 1의 비율은 그 안에 들어 있는 1의 개수를 길이로 나눈 값이다. 부분 문자열은 연속한 문자로 이루어지고 길이는 1 이상이다. 가장 가까운 부분 문자열 중 시작 위치가 가장 앞인 것의 위치를 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $F$가 공백 하나로 구분되어 주어진다. $F$는 0 이상 1 이하의 소수이고 소수점 아래가 정확히 6자리다. 다음 줄에는 0 또는 1인 숫자 $N$개가 공백 없이 이어져 주어진다.

제한

• $1 \le T \le 100$
• $0 \le F \le 1$
• $F$의 소수점 아래는 정확히 6자리다
• $1 \le N \le 500000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 1의 비율이 $F$에 가장 가까운 부분 문자열의 시작 위치다. 위치는 0부터 센다. 가능한 위치가 여러 개면 그중 가장 작은 값을 출력한다.

$F = 0.666667$이고 문자열이 001001010111인 경우를 보자. 1의 비율이 정확히 $666667/1000000$인 부분 문자열은 없고, 가장 가까운 값은 $2/3$이다. 이 값에 도달하는 부분 문자열은 5개다. 길이가 3이고 위치 5, 7, 8에서 시작하는 101, 101, 011, 그리고 길이가 6이고 위치 5, 6에서 시작하는 101011, 010111이다. 이 중 시작 위치가 가장 작은 값은 5다.