파도반 수열

파도반 수열 P(N)은 다음과 같이 정의된다.

• P(1) = 1, P(2) = 1, P(3) = 1
• P(N) = P(N-2) + P(N-3) (N ≥ 4)

N이 주어질 때 P(N)을 구하라.

입력

첫째 줄에 테스트 케이스 수 T가 주어진다. 이후 T개의 줄에 각각 N이 주어진다.

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100

출력

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

예제 입력 1

3
1
5
10

예제 출력 1

1
2
9