암벽 등반

암벽에는 자연이 만든 것이든 사람이 만든 것이든 손가락이나 발가락을 걸 수 있는 작은 구멍과 돌출부가 있다. 목표 지점까지 오르려면 힘만큼이나 계획이 필요하다. 한 번 움직이기 전에 그다음 동작에서 쓸 자리로 팔다리 하나를 옮길 수 있는지 미리 확인해야 하기 때문이다.

이 문제는 그 계획 과정을 다음과 같이 모형으로 만든다. 2차원 벽에 있는 지점 $n$개의 좌표가 주어진다. 한 지점에는 손 하나 또는 발 하나만 걸 수 있다. 한 번의 이동에서 팔다리 하나를 다른 지점으로 옮기며, 다음 규칙이 항상 성립해야 한다.

• 두 손 사이의 거리는 $2$ 이하이고, 두 발 사이의 거리도 $2$ 이하이다.
• 왼손과 왼발 사이의 거리는 $3$ 이하이고, 오른손과 오른발 사이의 거리도 $3$ 이하이다.
• 왼손과 오른발 사이의 거리는 $4$ 이하이고, 오른손과 왼발 사이의 거리도 $4$ 이하이다.
• 서로 다른 두 팔다리가 같은 지점에 놓이지 않는다.
• 두 발 모두 두 손보다 높지 않다. 즉 각 발의 $y$좌표는 각 손의 $y$좌표 이하이다.

처음에 왼발은 $1$번 지점, 오른발은 $2$번 지점, 왼손은 $3$번 지점, 오른손은 $4$번 지점에 있다. 시작 자세는 항상 규칙을 만족한다. 팔다리 중 하나가 $n$번 지점에 닿으면 벽을 다 오른 것이다. 팔다리 하나를 $n$번 지점에 올려놓는 데 필요한 최소 이동 횟수를 구하라.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. $K \ge 1$이다. 이어서 데이터 집합 $K$개가 다음 형식으로 주어진다.

각 데이터 집합의 첫째 줄에는 지점의 개수 $n$이 주어진다. $4 \le n \le 30$이다. 다음 줄에는 실수 $2n$개 $x_1$, $y_1$, $x_2$, $y_2$, ..., $x_n$, $y_n$이 주어지며, $(x_i, y_i)$는 $i$번 지점의 좌표이다.

각 데이터 집합마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 x는 데이터 집합의 번호이고 $1$부터 센다. 다음 줄에는 팔다리 하나가 $n$번 지점에 처음 닿을 때까지의 최소 이동 횟수를 출력한다. 어떤 방법으로도 $n$번 지점에 팔다리를 올려놓을 수 없으면 그 줄에 Impossible을 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.