## Tower of Hanoi puzzle solution using recursion-

### story-

The tower of Hanoi (also called the Tower of Brahma or the Lucas tower) was invented by a French mathematician Édouard Lucas in the 19th century. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests. In the legend, the young priests were given 64 gold disks stacked neatly on one of three posts. Each disk rested on a slightly larger disk. The priests' goal was to re-create the stack on a different post by moving disks, one at a time, to another post with the rule that a larger disk could never be placed on top of a smaller disk. Using mathematics, you can calculate that even when the priests found the most efficient way to solve the problem and moved the disks at a rate of one per second, it would take almost 585 billion years to finish the job. That is more than 40 times the age of the universe!

### Problem Statement->

The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack to another rod. You are given the number of discs N. Initially, these discs are in the rod 1. You need to print all the steps of discs movement so that all the discs reach the 3rd rod. Also, you need to find the total moves.

Note: The discs are arranged such that the top disc is numbered 1 and the bottom-most disc is numbered N. Also, all the discs have different sizes and a bigger disc cannot be put on the top of a smaller disc. Refer the provided link to get a better clarity about the puzzle.

Input:

The first line of input is T denoting the number of testcases. T testcases follow. Each testcase contains a single line of input containing N.

Output:

For each testcase, print the steps and the total steps taken. Please see the example output to see the steps format.

Constraints:

1 <= T <= 16

1 <= N <= 16

Example:

Input:

2

2

3

Output:

move disk 1 from rod 1 to rod 2

move disk 2 from rod 1 to rod 3

move disk 1 from rod 2 to rod 3

3

move disk 1 from rod 1 to rod 3

move disk 2 from rod 1 to rod 2

move disk 1 from rod 3 to rod 2

move disk 3 from rod 1 to rod 3

move disk 1 from rod 2 to rod 1

move disk 2 from rod 2 to rod 3

move disk 1 from rod 1 to rod 3

7

read story about tower of Hanoi

It is strongly recommended that you should try this problem before jumping to a solution Practice Your code Here to gfg- code now

### solution-

#### Thinking Approach-

This is very simple if I have only one block in the source. What I will do if I have only one block in my source tower I will not use a helper tower that time I will simply move my block from source to destination and count number of step in this case i will use only one step.tower of Hanoi visualization |

*recursion is a magical function.*