By UNESCO resolution the original Tower of Hanoi was subjected to restoration. Thereby during solution of the puzzle it is forbidden to move a disk from the first peg directly to the third peg and vice versa. Write a recursive procedure that prints a sequence of moves subject to such restrictions.

Input

One integer n (1 ≤ n ≤ 7) - the number of disks on the first peg.

Output

Print the sequence of moves for transferring all the rings to the third peg in the next order: number of the disk, starting peg, destination peg. Disks are numbered from the smallest to the largest. The number of moves should not exceed 105.