Background

在印度有一个古老传说，大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

Description

如图所示：

约定：A柱为起始柱，B柱为中转柱，C柱为目标柱

给定一个数字$n$代表圆盘的个数，并默认圆盘从上到下是符合从小到大的要求的。
求出$n$个圆盘需要多少步操作才能完全从A柱移动到C柱。并给出操作的过程。

$1<$n$<=8$

Format

Input

输入一个正整数数字$n$ ($1<$n$<=8$)

Output

输出操作圆盘的步骤

Samples

3

A->C
A->B
C->B
A->C
B->A
B->C
A->C

样例1解释

3个圆盘，即可通过输出的过程进行操作，将A柱的圆盘从小到大转移到C柱，满足题目需求。

Limitation

1s, 1024KiB for each test case.