알약

박종수 할아버지는 매일 약을 반 알씩 먹는다. 손녀 선영이가 약이 N알 담긴 병을 선물로 드렸다.

첫째 날, 할아버지는 병에서 약을 하나 꺼낸다. 이 약은 온전한 한 알이므로 반으로 쪼개어 한 조각(반 알)을 먹고, 남은 반 조각은 다시 병에 넣는다.

둘째 날부터는 병에서 약을 하나 꺼내는데, 꺼낸 것이 온전한 한 알일 수도 있고 이미 쪼갠 반 조각일 수도 있다. 반 조각이면 그대로 먹고, 온전한 한 알이면 반으로 쪼개어 한 조각을 먹고 남은 반 조각을 다시 병에 넣는다.

할아버지는 온전한 한 알을 꺼낸 날에는 손녀에게 문자로 W를, 반 조각을 꺼낸 날에는 H를 보낸다. 선영이는 받은 문자를 순서대로 종이에 기록한다. 병을 다 비우기까지는 정확히 $2N$일이 걸리므로, 길이가 $2N$인 문자열이 하나 만들어진다.

약을 꺼내는 순서에 따라 서로 다른 문자열이 만들어질 수 있다. 만들어질 수 있는 서로 다른 문자열은 모두 몇 개인가?

입력은 최대 1000개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄이며, 병에 담긴 약의 개수 $N$ ($N \le 30$)이 주어진다.

입력의 마지막 줄에는 0이 하나 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 만들어질 수 있는 서로 다른 문자열의 개수를 한 줄에 하나씩 출력한다.