#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0;i < n;i++) {
        cin >> arr[i];

        int dp[arr[i] + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int j = 4;j <= arr[i]+1;j++ ) {
            dp[j] = dp[j-1]+dp[j-2]+dp[j-3];
        }
        cout << dp[arr[i]] << "\n";
    }
    return 0;
}