육각형 타일

학교로 가는 메리의 길은 육각형 타일이 깔린 곧게 뻗은 길입니다.

타일들은 벽돌을 쌓듯 서로 어긋나게 배치되어 있어서, 모든 타일은 바로 뒤에 오는 두 타일과 각각 한 변씩 맞닿아 있습니다. 길의 맨 앞에는 웃는 얼굴이 그려진 특별한 타일이 있고, 나머지 타일에는 앞에서부터 차례대로 $1, 2, 3, \dots$ 번호가 오름차순으로 매겨져 있습니다.

학교에 갈 때 메리는 다음 규칙에 따라 타일을 밟습니다.

• 항상 웃는 얼굴 타일에서 출발합니다. 이 타일은 $1$번 타일 앞에 있으며 $1$번 타일과 $2$번 타일 모두와 맞닿아 있습니다.
• 지금 서 있는 타일보다 번호가 작은 타일로는 갈 수 없습니다. 즉 밟는 번호는 항상 커져야 합니다.
• 한 걸음은 반드시 이웃한 타일로만 갑니다. 배치 특성상 $k$번 타일에서는 앞으로 $k+1$번 또는 $k+2$번 타일로만 갈 수 있습니다.
• 반드시 번호가 가장 큰 타일에서 끝나야 합니다.

한 번의 이동 경로란 메리가 밟은 번호 타일들을 순서대로 나열한 것입니다. 메리는 같은 경로를 두 번 걷고 싶지 않습니다. 번호가 매겨진 타일이 $N$개(웃는 얼굴 타일 제외) 있을 때, 하루에 하나씩 가능한 모든 경로를 한 번씩 걸으려면 며칠이 걸릴까요?

예를 들어 타일이 $N = 4$개일 때 가능한 경로는 1-2-3-4, 1-2-4, 1-3-4, 2-3-4, 2-4 의 다섯 가지입니다.

$N$이 주어질 때 서로 다른 이동 경로가 몇 가지인지 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 타일의 개수를 나타내는 정수 $N$ ($1 \le N \le 40$) 하나가 적힌 한 줄입니다.

마지막 테스트 케이스 다음 줄에는 $0$ 하나만 주어지며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 서로 다른 이동 경로의 개수를 정수 하나로 한 줄에 출력합니다.