[Baekjoon] #9461 파도반 수열

 

import java.util.Scanner;

//Q)파도반 수열
//#9461

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int tc = sc.nextInt();
		long[] result = new long[tc];
		int n;
		long[] dp = new long[101];
		
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		
		for(int i=0;i<tc;i++){
			
			n = sc.nextInt(); // P(N) 파도반 수열 입력
			for(int j=3;j<=n;j++){
				dp[j] = dp[j-2]+dp[j-3];
			}
			
			result[i] = dp[n];
		}
		
		for(int i=0;i<tc;i++){
			System.out.println(result[i]);
		}
	}
}