파도반 수열(Padovan Sequence)은 나선 모양으로 삼각형을 붙여나가며 만들어지는 수열입니다.

첫 삼각형은 정삼각형으로 변의 길이는 1입니다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가합니다.

나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열을 나열해 보면 다음과 같습니다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 ...

자연수 N을 입력받아 N번째 파도반 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 입력된다.

출력

첫째 줄에 N번째 파도반 수를 출력한다.

제한 사항

• 1 ≤ N ≤ 60

예제 입력 1

10

예제 출력 1

9