Background

有三根柱子 $A$、$B$、$C$。$n$ 个从小到大的盘子一开始都叠在 $A$ 柱上。

Description

请把这 $n$ 个盘子全部搬到 $C$ 柱，可以借助 $B$ 柱。规则：

1. 一次只能搬动一个盘子；
2. 任何时候，大盘子都不能压在小盘子上面。

请输出搬动的每一步，最后再输出总共搬了多少步。

搬 $n$ 个盘子的递归想法：先把上面 $n-1$ 个搬到 $B$，再把最大的搬到 $C$，最后把 $n-1$ 个从 $B$ 搬到 $C$。

Format

Input

一行一个整数 $n$（$1 \le n \le 12$）。

Output

前若干行，每行形如 A->C，表示把一个盘子从某根柱子搬到另一根柱子。

最后一行输出 共 x 步（其中 $x$ 是搬动的总步数，注意“共”和“步”之间各有一个空格）。

Samples

3

A->C
A->B
C->B
A->C
B->A
B->C
A->C
共 7 步

Hint

总步数是 $2^n - 1$。这道题用循环几乎写不出来，递归却只要三步，是递归“魔法感”最强的一题。

Limitation

1s, 256MiB for each test case.