크래커 배럴 게임

인기 있는 시골 잡화점 체인 Cracker Barrel은 음식이 나올 때까지 손님들이 즐길 수 있도록 펙 게임을 제공한다. 게임은 15칸짜리 보드에서 진행된다. 규칙은 간단하다. 한 번의 이동에서 말 하나가 다른 말 위를 뛰어넘어 빈 칸으로 간다. 뛰어넘긴 말은 보드에서 제거된다. 말이 하나만 남으면 플레이어가 이긴다. 보통 게임은 말 14개와 빈 칸 하나로 시작한다. 말에는 파랑, 빨강, 노랑, 흰색이 있을 수 있지만, 보통 말의 색은 중요하지 않다.

이 문제에서는 여러 색의 말 1개 이상 14개 이하로 된 시작 배치와 목표 색이 주어진다. 일반 규칙에 따라 보드에서 말을 하나만 남을 때까지 제거하고, 마지막에 남은 말이 목표 색이 되도록 할 수 있는지 판단한다.

여러 개의 테스트 케이스가 입력된다. 각 테스트 케이스는 한 줄에 목표 말을 나타내는 두 글자가 주어지고, 이어서 보드의 초기 배치가 주어진다. 말은 대문자 두 글자로 나타내며, 예를 들어 BB는 파란색 말을 뜻한다. 첫 번째 행부터 네 번째 행까지는 각각 4, 3, 2, 1칸의 공백으로 들여쓰기 한다.

**가 적힌 줄이 나오면 입력이 끝난다.

각 테스트 케이스에 대해, 말을 하나만 남을 때까지 유효한 이동을 거쳐 제거하면서 목표 색의 말이 남을 수 있으면 Possible을, 그렇지 않으면 Impossible을 출력한다.