有向无环图（Directed Acyclic Graph，简称 DAG）正如其名，是不包含环的有向图。

如果在这样的图中选择两个顶点，我们可以计算这两个顶点之间存在多少条不同的有向路径。我们认为两条路径不同，当且仅当其中一条路径包含另一条路径所不包含的边。

你的任务是创建一个包含 $n$ 个顶点（编号从 1 到 $n$）的有向无环图，使得从顶点 1 到顶点 $n$ 恰好有 $k$ 条路径。但这里有几个限制：你的图最多只能有 100 个顶点，每个顶点最多只能有两条出边，且图中不能包含重边（即如果某个顶点有两条出边，它们必须指向不同的顶点）。可以证明，对于满足下述限制的每一个可能的 $k$，都能够构建出一个满足这些条件的图。

输入格式

输入的第一行包含一个整数 $k$ ($1 \le k \le 10^9$)。

输出格式

第一行输出一个整数 $n$ ($2 \le n \le 100$)，表示图中顶点的数量。

接下来的 $n$ 行，每行包含两个整数。第 $i$ 行的两个整数表示从顶点 $i$ 出发的边所指向的顶点编号。如果某条边不存在，你可以将其设为 $-1$。如果某一行中的两个数字都不为 $-1$，则它们必须互不相同。

如果存在多个满足条件的图，你可以输出其中任意一个。请注意，你不需要最小化图中顶点的数量，只需满足顶点数量的限制即可。

样例

输入 1

3

输出 1

6
3 5
6 -1
2 6
2 6
6 -1
-1 -1

说明 1

下图展示了输出中描述的 6 顶点图。从顶点 1 到顶点 6 的路径有：$1 \to 3 \to 2 \to 6$，$1 \to 3 \to 6$ 以及 $1 \to 5 \to 6$。