Towers of Hanoi Grid

Towers of Hanoi is a rather famous problem for computer scientists as it is an excellent exercise in recursion. For those unfamiliar, here is the classic problem. You are given three pegs. On the first peg, there are $d$ disks stacked in decreasing order of size. The objective of the game is to move the entire tower from the first peg to the last peg. In each move, you may only move a single disk from the top of one stack to another stack. For the entire game, no disk of larger size is ever allowed to be placed on top of a disk of smaller size. The goal of the puzzle is to move the tower in the minimum number of moves.

In this problem, the pegs form an $n \times n$ grid. The rows are numbered top to bottom from $1$ to $n$, and the columns are numbered left to right from $1$ to $n$. The original tower is placed on the top left peg $(1, 1)$. The goal is to move the tower to the bottom right peg $(n, n)$ in the minimum number of moves possible.

The game has some different but related rules:

• From peg $(r, c)$, you may only move the top-most disk to peg $(r + 1, c)$ or peg $(r, c + 1)$, and only if that peg exists.
• Only pegs $(1, 1)$ and $(n, n)$ may have more than one disk at any time. All other pegs may hold at most one disk.
• You can choose any peg for each move.
• You still may never place a larger disk on a smaller disk.

The first input line contains a positive integer $g$, the number of grids to solve. The grids follow on the next $g$ lines, one grid per line. Each grid is described by two integers $d$ and $n$ ($2 \le d \le 100$, $2 \le n \le 100$), the number of disks and the dimensions of the grid.

For each grid, output Grid #d: v, where $v$ is the minimum number of moves to solve the Tower of Hanoi Grid puzzle. If it is not possible to move the disks from peg $(1, 1)$ to peg $(n, n)$, output impossible for $v$. Leave a blank line after the output for each grid.