题目背景

翻译自 CSES-2165 题。

题目描述

汉诺塔问题：有三根柱子（编号 1、2、3），第一根柱子上有 $n$ 个圆盘，从大到小叠放。你的任务是把所有圆盘从柱子 1 移到柱子 3，每次只能移动一个圆盘，且大盘不能放在小盘上面。输出最少步数的移动方案。

输入格式

输入一个整数 $n$。

输出格式

第一行输出最少步数，接下来每行输出两个整数 $a\ b$，表示把一个圆盘从柱子 $a$ 移到柱子 $b$。

样例

2

3
1 2
1 3
2 3

说明/提示

$1 \le n \le 16$。