Contest1337/E.java

import java.util.Scanner;

/**
 * Created by chshru on 2017/11/4.
 */
public class E {

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);
        int[] dp = new int[500005];
        init(dp);
        int t = cin.nextInt();
        while (t-- > 0) {
            int n = cin.nextInt();
            System.out.println(dp[n]);
        }
        cin.close();
    }

    private static void init(int[] dp) {
        int MOD = 998244353;
        dp[0] = 1;
        for (int i = 0; i < 500000; i++) {
            dp[i + 1] = (dp[i] + dp[i + 1]) % MOD;
            dp[i + 2] = (dp[i] + dp[i + 2]) % MOD;
            dp[i + 3] = (dp[i] + dp[i + 3]) % MOD;
        }
    }
}