Theater

There are N actors. A scene is represented by the set of actors standing on the stage. A play consists of K consecutive scenes and must satisfy all of the following conditions.

1. At least one actor must be on stage in every scene.
2. The set of actors on stage cannot change during a scene.
3. When moving from one scene to the next, exactly one actor moves. The move is either one off-stage actor entering the stage or one on-stage actor leaving it.
4. The stage is empty before the play starts and after it ends. Therefore, the first and last scenes each contain exactly one actor.
5. No two different scenes may have the same set of actors.
6. The number of scenes K must be as large as possible.

Given N, write a program that constructs a longest possible play.

The first line contains a positive integer N. (2 ≤ N ≤ 17) The actors are numbered from 1 to N.

On the first line, print the maximum possible number of scenes K.

On the second line, print the number of the actor who enters the stage to form the first scene.

On each of the next K-1 lines, print the number of the actor who moves when transitioning from the current scene to the next scene. If that actor is off stage, they enter; if that actor is on stage, they leave.

On the last line, print the number of the actor who leaves the stage after the last scene. If there is more than one valid construction, print any one of them.