뒤집기 게임

뒤집기 게임은 4×4 크기의 판 위에서 진행되며, 16개의 각 칸에는 양면 말이 하나씩 놓여 있습니다. 각 말의 한쪽 면은 흰색이고 반대쪽 면은 검은색이며, 처음에는 검은 면 또는 흰 면 중 하나가 위를 향한 채 놓여 있습니다.

한 차례마다 3개에서 5개의 말을 뒤집으며, 뒤집힌 말은 위를 향한 면의 색이 검은색에서 흰색으로, 또는 흰색에서 검은색으로 바뀝니다. 뒤집을 말은 매 차례 다음 규칙에 따라 정합니다.

1. 16개의 말 중 하나를 고릅니다.
2. 고른 말과 그 말의 위, 아래, 왼쪽, 오른쪽에 인접한 말(존재하는 경우)을 모두 뒤집습니다.

예를 들어 다음 배치를 생각해 봅시다.

bwbw
wwww
bbwb
bwwb

여기서 'b'는 검은 면이 위를 향한 말을, 'w'는 흰 면이 위를 향한 말을 뜻합니다. 만약 3번째 줄의 1번째 말을 골라 뒤집으면(위 그림에 표시된 선택), 판은 다음과 같이 바뀝니다.

bwbw
bwww
wwwb
wwwb

게임의 목표는 모든 말을 흰 면이 위를 향하게 만들거나, 모든 말을 검은 면이 위를 향하게 만드는 것입니다. 주어진 배치에서 이 목표를 달성하는 데 필요한 최소 차례 수를 구하는 프로그램을 작성하세요.

네 줄이 주어지며, 각 줄은 판의 한 행을 나타내는 4개의 문자 'w' 또는 'b'로 이루어집니다.

목표를 달성하는 데 필요한 최소 차례 수를 정수 하나로 출력합니다. 처음부터 이미 목표가 달성되어 있으면 0을 출력합니다. 목표를 달성하는 것이 불가능하면 따옴표 없이 단어 "Impossible"을 출력합니다.