15989번

15989

#include <iostream>

using namespace std;

int main() {
    int dp[10001][4];

    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[3][1] = 1;
    dp[3][2] = 1;
    dp[3][3] = 1;

    int t;
    cin>>t;
    int n;
    for(int i=0;i<t;i++) {
        cin>>n;
            for(int k=4;k<=n;k++) {
                dp[k][1] = dp[k-1][1];
                dp[k][2] = dp[k-2][1] + dp[k-2][2];
                dp[k][3] = dp[k-3][1] + dp[k-3][2] + dp[k-3][3];
            }
            int sum = dp[n][1] + dp[n][2] + dp[n][3];
            cout<<sum<<endl;
    }
}