10082 파도반 수열 Silver III

문제

파도반 수열 P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2이고, P(N) = P(N-2) + P(N-3) (N ≥ 4)이다.

N이 주어질 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스 수 T가 주어진다. 각 줄에 N (1 ≤ N ≤ 100)이 주어진다.

출력

각 테스트 케이스마다 P(N)을 출력한다.

5
1
2
6
11
12

1
1
3
16
21