하노이의 탑 격자

하노이의 탑은 재귀를 연습하기에 아주 좋은 문제라서 컴퓨터 과학자들 사이에서 꽤 유명하다. 잘 모르는 사람을 위해 고전 문제를 설명하면 다음과 같다. 막대가 세 개 있다. 첫 번째 막대에는 크기가 작아지는 순서로 쌓인 원반 $d$개가 있다. 게임의 목표는 탑 전체를 첫 번째 막대에서 마지막 막대로 옮기는 것이다. 한 번의 이동에서는 한 더미의 맨 위에 있는 원반 하나만 다른 더미로 옮길 수 있다. 게임 내내 큰 원반을 작은 원반 위에 올릴 수는 없다. 퍼즐의 목표는 최소 횟수로 탑을 옮기는 것이다.

이 문제에서 막대는 $n \times n$ 격자를 이룬다. 행은 위에서 아래로 $1$부터 $n$까지, 열은 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호가 붙는다. 원래 탑은 왼쪽 위 막대 $(1, 1)$에 놓여 있다. 목표는 가능한 한 적은 횟수로 탑을 오른쪽 아래 막대 $(n, n)$으로 옮기는 것이다.

이 게임에는 몇 가지 다르지만 관련된 규칙이 있다.

• 막대 $(r, c)$에서는 맨 위 원반을 막대 $(r + 1, c)$ 또는 막대 $(r, c + 1)$로만 옮길 수 있으며, 그 막대가 존재할 때에만 가능하다.
• 어느 순간에든 여러 개의 원반을 둘 수 있는 막대는 $(1, 1)$과 $(n, n)$뿐이다. 나머지 막대에는 최대 한 개의 원반만 놓을 수 있다.
• 각 이동에서 어떤 막대든 고를 수 있다.
• 그래도 큰 원반을 작은 원반 위에 올릴 수는 없다.

첫 줄에는 풀어야 할 격자의 개수인 양의 정수 $g$가 주어진다. 이어서 $g$개의 줄에 격자가 한 줄에 하나씩 주어진다. 각 격자는 두 정수 $d$와 $n$으로 표현되며($2 \le d \le 100$, $2 \le n \le 100$), $d$는 원반의 개수, $n$은 격자의 크기이다.

각 격자에 대해 Grid #d: v 형식으로 출력한다. 여기서 $v$는 하노이의 격자 퍼즐을 푸는 데 필요한 최소 이동 횟수이다. 막대 $(1, 1)$에서 막대 $(n, n)$으로 원반을 옮길 수 없다면 $v$ 자리에 impossible을 출력한다. 각 격자의 출력 뒤에는 빈 줄을 하나 남긴다.