문제1063--계단 오르기

1063: 계단 오르기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

평소 운동이 부족하다고 생각한 유정이는 계단 오르기 운동을 하려고 결정 했습니다. 키가 작고 다리가 짧아서 한번에 여러 계단을 오를 수 없었고, 몇 번의 테스트로 한번에 두칸이 안정적으로 오를 수 있는 최대 칸 수 라는걸 깨달았습니다.

운동을 언제까지 할지 결정을 할 필요가 있던 유정이는 매번 서로 다른 방식으로 계단을 오르고, 더이상 새로운 방법으로 계단을 오를 수 없을 때 까지 운동을 하기로 결정을 했습니다.

만약 계단이 5칸 이라면 유정이가 오를 수 있는 방법은
1) 1 - 1 - 1 - 1 - 1
2) 1 - 2 - 1 - 1
3) 1 - 2 - 2
4) 1 - 1 - 2 - 1
5) 1 - 1 - 1 - 2
6) 2 - 1 - 1 - 1
7) 2 - 2 - 1
8) 2 - 1 - 2

으로 총 8가지 방법으로 오를 수 있습니다.

유정이를 위해 오를 수 있는 총 가짓수를 구해주는 프로그램을 만들 어 주세요.

입력 설명

첫 줄엔 테스트 케이스의 수 T (1 <= T <= 25)가 주어지며, 그 다음 줄 부터는 계단의 수 N ( 1 <= N <= 25)이 T개 주어집니다.

출력 설명

한 줄에 하나씩 계단을 오르는데 몇 가지 방법이 있는지 출력 해 주세요.

입력 예시 Copy

2
11
24

출력 예시 Copy

144
75025

출처/분류