有一个 $4 \times n$ 的棋盘。所有行从 1 到 4 编号，所有列从 1 到 $n$ 编号。棋盘上的每个方格可以用坐标 $[r, c]$ 来描述，其中 $r$ 是行号，$c$ 是列号。

此外，有一个国际象棋马（knight）位于方格 $[1, 1]$。下图展示了一个 $4 \times n$ 棋盘及上面的马：

马的目标是进行一次遍历，从 $[1, 1]$ 出发并回到 $[1, 1]$。马在遍历过程中应访问每个方格（$[1, 1]$ 除外）恰好一次。

国际象棋中的马可以从一个方格移动到水平移动两格且垂直移动一格，或者垂直移动两格且水平移动一格的方格。因此，完整的移动路径看起来像字母 L。

你需要编写一个程序，找出马在遍历中能访问到的不同方格的最大数量，并输出该遍历路径。

输入

输入仅包含一个整数 $n$ ($2 \le n \le 10^4$)，表示棋盘的列数。

输出

第一行输出马能够访问到的最大方格数量 $m$，要求遍历时除 $[1, 1]$ 外每个方格仅访问一次。

第二行输出最优遍历路径中访问方格的坐标。所有坐标应按 $r_1 \ c_1 \ r_2 \ c_2 \ \dots \ r_m \ c_m \ r_1 \ c_1$ 的格式打印。坐标应在一行内打印，中间仅用空格分隔，不换行。

样例

输入格式 1

6

输出格式 1

22
1 1 2 3 1 5 3 6 2 4 1 2 3 1 4 3 3 5 1 4 2 2 4 1 3 3 4 5 2 6 3 4 4 2 2 1 1 3 2 5 4 4 3 2 1 1