# Towers of Hanoi P85288

Statement html

[r] The Towers of Hanoi is a game that consists of three rods and n disks of different sizes that can slide onto any rod. The game starts with the disks stacked in order of size on the left rod, the biggest disk at the bottom. The aim of the game is to move all the disks from the left rod (A) to the right rod (C), using the middle rod (B) as auxiliary. All the moves have to follow these rules:

• In each step, only one disk can be moved.
• Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, over the other disks that may already be present on that rod.
• No disk can be placed over a smaller disk.

Write a program that solves the game of the Towers of Hanoi, using the minimal number of movements.

Input

Input consists of a single natural number n between 1 and 18.

Output

Print the shortest sequence of movements for the given n. Follow the format of the examples.

Public test cases
• Input

```1
```

Output

```A => C
```
• Input

```2
```

Output

```A => B
A => C
B => C
```
• Input

```3
```

Output

```A => C
A => B
C => B
A => C
B => A
B => C
A => C
```
• Information
Author
Jordi Petit
Language
English
Translator
Carlos Molina
Original language
Catalan
Other languages
Catalan
Official solutions
C++ Java Python
User solutions