Tower of Hanoi

There are three pegs, numbered 1, 2 and 3. n disks of different sizes start stacked on peg 1, the biggest at the bottom. You may move one disk at a time from the top of one peg to another peg, and you may never put a bigger disk on a smaller one.

Return the list of moves, each written [from_peg, to_peg], that shifts all the disks to peg 3 using the fewest moves. (The shortest solution is unique.)

Examples

Example 1

Input:

tower_of_hanoi(2)

Output:

[[1, 2], [1, 3], [2, 3]]

Example 2

Input:

tower_of_hanoi(0)

Output:

[]

Constraints

• 0 <= n <= 14
• The answer has 2^n - 1 moves.