Brick Wall Patterns

원문 : http://acm.uva.es/p/v9/900.html

높이가 폭의 2배인 벽돌을 이용해서 담을 쌓고자 한다. 담의 높이는 벽돌의 높이와 동일하고, 길이는 원하는 길이로 해서 담을 쌓는다.  다음 그림을  보면..

- 담의 길이를 기본 1 (벽돌 한개의 폭)으로 하는 방법: 벽돌 하나를 세워두는 한가지 패턴
- 담의 길이를 2으로 하는 방법: 벽돌 두개를 세워두는 방법과 눞혀두는 두가지 패턴
- 담의 길이를 3으로 하는 방법은 3가지 패턴이 있다.

문제
담의 길이가 주어졌을 때, 몇개의 패턴으로 담을 쌓을 수 있는지를 구하라.입력한 줄에 한개씩 담의 길이를 의미하는 양의 수가 입력된다. 담의 길이는 퇴대 50이며 0을 입력하면 입력이 종료된다.

입력 예시
1
2
3
0

출력 예시
1
2
3