题目描述

汉诺塔是一种非常著名的游戏。汉诺塔包括三根柱子和一些圆盘。这些圆盘一开始按照从高到低，从小到大的顺序排列，形成圆锥状的“塔”。解题者的目标是将所有的圆盘按照一开始的顺序放到另一根柱子上。但是，移动的时候，你要遵守以下三条规则：

• 每次只能移动一个圆盘。
• 每次移动时只能拿走任意杆上最顶端的圆盘，并将它移动到另一根杆子上。
• 两个相邻的圆盘不能出现上面的圆盘比下面的圆盘要大的情况。

【输入格式】

输入仅一行，为一个整数n：表示圆盘数。

【输出格式】

第一行输出一个整数k：表示最小移动次数。

之后，输出描述动作的k行。每行有两个整数a和b：将圆盘从栈 a移动到栈b。

样例 #1

样例输入 #1

2

样例输出 #1

3
1 2
1 3
2 3

样例 #2

样例输入 #2

3

样例输出 #2

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3