#825. Tower of Hanoi: the moves
Print the moves that carry n disks from peg 1 to peg 3, one per line, as `1 -> 3` (use the standard recursive algorithm).
### Input
n (1 ≤ n ≤ 6).
### Output
Answer.
Examples
Input
1
Output
1 -> 3
Input
5
Output
1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3 1 -> 2 3 -> 2 3 -> 1 2 -> 1 3 -> 2 1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3 2 -> 1 3 -> 2 3 -> 1 2 -> 1 2 -> 3 1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.