연극극단 "월드"는 2009년 새해를 맞아 새로운 연극을 기획 중이다. 이 연극에는 새로운 오디션을 통해 선발된 N명의 신인 배우들만이 출연할 예정이다. 극단을 운영하고 있는 김형택 사장의 지시에 따라, 당신은 아래의 조건을 만족시키는 참신한 연극을 만들어야 한다.</p>

1. 연극은 연속된 K개의 장면으로 구성되게 된다. 그리고 각 장면에는 적어도 한 명 이상의 배우가 무대에 서 있어야 한다.
2. 하나의 장면이 계속되는 동안에는 무대에 서는 배우들이 바뀔 수 없다. 즉 장면 중간에 새로운 배우가 무대로 나오거나, 무대에 있던 배우가 무대 뒤로 들어가는 일은 없다.
3. 무대가 혼란스러워지는 것을 방지하기 위해, 한 장면이 끝나고 다음 장면으로 넘어갈 때에는 단 한 명의 배우만 이동해야 한다. 즉 새로운 배우 하나가 무대로 나오거나, 무대에 있던 배우 하나가 무대 뒤로 들어가는 경우만이 허용된다.
4. 연극이 시작되기 전과, 연극이 끝나고 난 후에는 무대가 비어 있어야 한다. 따라서 첫 번째 장면과 마지막 장면에서는 무대 위에 한 명의 배우만이 있어야 한다.
5. 각 장면에서 무대에 서는 배우들의 구성은 장면마다 달라야 한다. 예를 들어 한 장면에서 배우 2, 배우 3, 배우 5가 출연했다면, 동일한 세 명의 배우가 무대에 서는 장면이 있어서는 안 된다.
6. 신인 배우들에게 보다 많은 기회를 주기 위해, 연극은 가능한 많은 장면으로 구성되어 있어야 한다. 즉 K를 최대로 해야 한다.

예를 들어 N=2인 경우, 아래와 같이 연극을 구성하면 모든 조건을 만족시키게 된다.

• 연극이 시작되기 전:
  • (배우 1) 무대로
  </li>
• 첫 번째 장면: (배우 1)
  • (배우 2) 무대로
  </ul> </li>
  • 두 번째 장면: (배우 1), (배우 2)
    • (배우 1) 뒤로
    </ul> </li>
    • 세 번째 장면: (배우 2)
      • (배우 2) 뒤로
      </ul> </li>
      • 연극이 끝나고 난 후: 
      </ul>

      배우의 수가 주어지면, 극단의 매니저 김수현을 도와 연극을 구성하는 프로그램을 작성하시오.

      입력 형식

      첫째 줄에 자연수 N이 주어진다. (2 ≤ N ≤ 17) 신인 배우들은 1부터 N까지 순서대로 번호가 매겨진다.

      출력 형식

      첫째 줄에 조건을 만족시키는 최대의 장면 수 K를 출력한다. 두 번째 줄에는 첫 번째 장면에 무대로 나올 배우의 번호를 출력한다. 세 번째 줄부터 K-1개 줄에 걸쳐 각 장면이 끝나고 다음 장면으로 넘어갈 때 무대로 나오거나 무대 뒤로 들어가는 배우의 번호를 출력한다. K+2번째 줄에는 마지막 장면에서 무대에 서게 되는 배우의 번호를 출력한다. 연극을 구성하는 방법이 둘 이상이면 아무 것이나 하나 출력한다.

      예제 입력

      2

      예제 출력

      3
      1
      2
      1
      2