You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-2165 题。

题目描述

汉诺塔的游戏包括三组(左，中和右)共 $n$ 个不同大小的圆盘。最初，左边的柱子拥有所有的圆盘，按照从上到下的大小顺序递增，即从上到下圆盘的大小是依次变大的。

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

你的任务是找到一个解决方案，最大限度地减少移动的数量。

输入格式

输入一个正整数 $n$。

输出格式

第一行输出一个整数 $k$ 表示最少的移动次数。

接下来有 $k$ 行，每行输出两个整数 $a,b$ 表示将圆盘从 $a$ 柱子移动到 $b$ 柱子。柱子从左到右依次编号为 $1,2,3$。

样例

2

3
1 2
1 3
2 3

说明/提示

$1\le n \le 16$。