시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 136 75 65 58.036%

문제

KAIST 주변에서 먹을 수 있는 배달 음식들은 대부분 치킨이다. 이렇게 치킨집이 포화 상태지만 지훈이는 카이스트 주변에 새로 치킨집을 창업했는데, 생각보다 장사가 잘 되었다!

알고 보니 그가 차린 치킨집의 신기한 방식 때문에 장사가 잘 된다고 한다. 지훈이의 치킨집에 치킨 주문을 하는 것은 간단하다. 어차피 지훈이네 치킨집의 메뉴는 도깨비오븐구이 하나이므로, 치킨 먹을 사람 수만 이야기하면, 그 사람 수에 맞는 치킨을 배달하는 것이다.

치킨의 마리 수를 정하는 방법은 다음과 같다:

  1. 2 인 1 닭, 3 인 2 닭, 5 인 3 닭, 8 인 5 닭, 13 인 8 닭 … 등 피보나치 수열의 인접한 두 수를 이용해(항상 사람의 수 > 닭의 수가 되어 야 한다) 치킨 세트를 만든다.
  2. 이 세트들을 적절히 조합해서 총 합이 정확히 N 인분이 되도록 만든다.
  3. 2 번 과정에서 조합한 세트들을 배달한다.

어느 날, 지훈이의 치킨집 단골인 태영이가 N 명이 먹을 것을 주문하면 배달되는 치킨 수의 범위가 궁금해졌다. 똑같이 N 인분을 주문한다고 해서 항상 같은 마리수의 닭이 오는 것은 아니기 때문이다. 예를 들어, N=6 일 경우, “2 인 1 닭” 세트를 3 개 배달하면 총 3 마리가 오는 반면, “3 인 2 닭” 세트를 2 개 배달하면 총 4 마리까지 올 수도 있다. 태영이는 이미 답을 알고 있으나 계산하기 귀찮은 나머지 여러분들에게 프로그램을 만들라고 시켰다.

치킨은 좋아하는 여러분들도 답이 궁금할 것이라고 생각되므로 이 문제를 풀어보자. N 이 주어졌을 때 배달되는 치킨 수의 최솟값과 최댓값을 구하면 된다.

입력

첫째 줄에 사람의 수 N 이 주어진다. N 은 현재 재학 중인 카이스트 학생 수보다는 작거나 같은 2 이상의 정수이다.

출력

배달되는 치킨 수의 최솟값과 최댓값을 띄어쓰기로 구분하여 출력한다.

예제 입력

6

예제 출력

3 4

힌트