회문 없는 문자열

문자 0, 1, ?으로 구성된 문자열 $\mathbf{S}$이 주어진다. 각 ?를 0 또는 1으로 바꿀 수 있다. 각 ?에 0 또는 1을 할당하여, 결과 문자열에 길이가 $5$ 이상인 회문 부분 문자열이 없도록 할 수 있는지 알아내야 한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$은 문자 0, 1, ?으로만 구성된다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 15$.

테스트 세트 2

시간 제한: 90초. $1 \le \mathbf{N} \le 5 \times 10^4$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 구성된다. 각 테스트 케이스의 첫 줄에는 문자열 $\mathbf{S}$의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다. 각 테스트 케이스의 둘째 줄에는 길이가 $\mathbf{N}$인 문자열 $\mathbf{S}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호이고(1부터 시작), 길이가 $5$ 이상인 회문 부분 문자열이 없는 결과 문자열을 만들 수 있다면 $y$은 POSSIBLE이고, 그렇지 않으면 IMPOSSIBLE이다.

예제 케이스 #1에서 전체 문자열이 회문이 되는 것을 막으려면 첫 번째 물음표와 마지막 물음표가 서로 다른 문자여야 한다.

첫 번째 물음표를 0로 바꾸고 마지막 물음표를 1로 바꾸면 1000?1001을 얻는다. 남은 ?를 1로 바꾸면 100011001을 얻고, 이때 처음 $5$개의 문자가 길이 $5$의 회문을 이룬다. 그렇지 않으면 100001001을 얻고, 처음 $6$개의 문자가 길이 $6$의 회문이다.

첫 번째 물음표를 1로 바꾸면 1001?0001을 얻는다. 남은 ?를 1로 바꾸면 100110001을 얻고, 이때 마지막 $5$개의 문자가 길이 $5$의 회문을 이룬다. 그렇지 않으면 100100001을 얻고, 마지막 $6$개의 문자가 길이 $6$의 회문이다.

따라서 유효한 문자열을 얻을 방법은 없다.

예제 케이스 #2에서 모든 ?를 바꾼 뒤 얻을 수 있는 유효한 문자열 중 하나는 10011이다.