말 옮기기
시간 제한1초메모리 제한128 MB
15개 구멍 삼각 보드에서 줄지어 선 핀들을 한 번에 뛰어넘어 시작 빈 구멍에 핀 하나만 남기는 최소 이동 횟수를 구합니다.
문제
삼각형 모양의 게임판에 구멍이 15개 있습니다. 구멍은 5개의 줄로 놓여 있고, 위에서 아래로, 각 줄에서는 왼쪽에서 오른쪽으로 다음과 같이 번호가 매겨져 있습니다.
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
처음에는 한 구멍만 비어 있고, 나머지 구멍에는 말(peg)이 하나씩 놓여 있습니다.
한 번의 이동은 다음과 같습니다. 말 하나와, 그 말을 지나는 직선 하나(가로줄 방향, 또는 두 대각선 방향 중 하나)를 고릅니다. 그 직선을 따라 말 바로 옆 칸부터 말이 한 개 이상 연달아 놓여 있고, 그 말들 바로 다음 칸이 비어 있으면, 고른 말은 그 말들을 뛰어넘어 비어 있는 칸에 내려앉습니다. 뛰어넘은 말은 모두 판에서 없어집니다. 한 번의 이동으로 여러 개의 말을 한꺼번에 뛰어넘을 수 있으며, 그렇더라도 이동 횟수는 1로 셉니다.
예를 들어 5번 칸만 비어 있을 때, 12번 칸의 말은 8번 칸의 말을 뛰어넘어 5번 칸에 내려앉을 수 있고(8번 말이 없어짐), 대신 14번 칸의 말은 9번 칸의 말을 뛰어넘어 5번 칸에 내려앉을 수 있습니다(9번 말이 없어짐).
처음에 비어 있던 바로 그 구멍에 말 하나만 남도록, 가능한 한 적은 이동 횟수로 판을 정리하는 것이 목표입니다. 필요한 최소 이동 횟수를 출력하세요. 어떤 방법으로도 불가능하면 IMPOSSIBLE을 출력합니다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어집니다. 이어지는 개의 줄에는 각각 정수 하나가 주어지며, 처음에 비어 있는 구멍의 번호(부터 까지)를 뜻합니다.
출력
각 테스트 케이스마다 한 줄에, 처음에 비어 있던 구멍에 말 하나만 남기기 위해 필요한 최소 이동 횟수를 출력합니다. 어떤 방법으로도 불가능하면 IMPOSSIBLE을 출력합니다.