宁宁现在在建设大楼！

在宁宁的规划中，大楼有 $n$ 层，从下到上依次为第 $1, 2, \cdots, n$ 层，她还要建设 $m$ 个电梯，每个电梯一定会停在第 $1$ 层和第 $n$ 层，她可以选择让这些电梯停在中间某些层（也可以不停）。她希望建设的这 $m$ 个电梯满足：对于任意不同的两层 $x, y$，存在一个电梯使 $x, y$ 可以直达（中间不经过任何可以停的层）。为了降低建造成本，她希望电梯数 $m$ 尽量小。

宁宁她不太聪明，于是她转过来求助你，希望你能告诉她 $m$ 的最小值并给出构造。

你不需要最小化停的总层数。但还是为了节约资源，你需要使得停的总层数不超过 $2 \times 10^6$。

Input

一行一个正整数 $n$ $(2 \le n \le 1000)$。

Output

第一行一个正整数 $m$，表示最少需要的电梯数。

接下来 $m$ 行，每行表示一个电梯的停层状况。具体来说，对于第 $i$ 行，你需要输出一个序列 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$，使得 $1 = a_{i, 1} < a_{i, 2} < \cdots < a_{i, k_i} = n$，且 $\sum\limits_{i=1}^m k_i \le 2 \times 10^6$。表示第 $i$ 个电梯会停在 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$ 层。

输出量较大，建议采用较快的输出方式。

Examples

Input 1

4

Output 1

4
1 3 4
1 4
1 2 3 4
1 2 4

Note

可以证明 $m$ 的最小值为 $4$。

第 $1, 2$ 层可以通过电梯 $3, 4$ 直达，第 $1, 3$ 层可以通过电梯 $1$ 直达，第 $1, 4$ 层可以通过电梯 $2$ 直达，第 $2, 3$ 层可以通过电梯 $3$ 直达，第 $2, 4$ 层可以通过电梯 $4$ 直达，第 $3, 4$ 层可以通过电梯 $1, 3$ 直达。