题目描述

汉诺塔游戏由三个栈（左、中、右）和n个不同大小的圆盘组成。最初，左侧栈包含所有圆盘，大小为从上到下依次递增。

目标是使用中间栈将所有圆盘移动到右侧栈。每次移动时，都可以将最上面的圆盘从一个栈移动到另一个栈。此外，不允许将较大的圆盘放置在较小的圆盘上。

请用程序找到一个能最大限度减少移动次数的解决方案。

输入格式

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

输出格式

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

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

2

3
1 2
1 3
2 3

数据范围与提示

【样例1说明】 在这个示例中，共有两个圆盘。输出显示了将所有圆盘从左堆栈（标记为 1）移动到右堆栈（标记为 3）的最少步骤，使用中堆栈（标记为 2）作为辅助。总共需要 3 步。

$1≤n≤16$