staircase.cpp

int calculate_steps1(int stp)
{
    if (stp == 0)
        return 1;
    if (stp == 1)
        return 1;
    if (stp == 2)
        return 2;
    
    return calculate_steps1(stp - 3) + calculate_steps1(stp - 2) + calculate_steps1(stp - 1);
}

int calculate_steps2(int stp, vector<int> &vec)
{
    if (vec[stp] != 0)
        return vec[stp];
    
    vec[stp] = calculate_steps2(stp - 3, vec) + calculate_steps2(stp - 2, vec) + calculate_steps2(stp - 1, vec);
    return vec[stp];
}

int calculate_util(int stp)
{
    vector<int> vec(stp + 1);
    for (size_t i = 0; i <= stp; i++)
        vec[i] = 0;
    
    vec[0] = 1;
    vec[1] = 1;
    vec[2] = 2;
    return calculate_steps2(stp, vec);
}

int calculate_steps(int stp)
{
    if (stp == 0)
        return 0;
    
    vector<int> t(stp + 1);
    t[0] = 1;
    t[1] = 1;
    t[2] = 2;
    for (size_t i = 3; i <= stp; i++) {
        t[i] = t[i - 3] + t[i - 2] + t[i - 1];
    }
    return t[stp];
}

int calculate_steps3(int stp)
{
    if (stp == 0)
        return 0;
    
    vector<int> t(3);
    t[0] = 1;
    t[1] = 1;
    t[2] = 2;
    
    if (stp < 3)
        return t[stp];

    for (size_t i = 3; i <= stp; i++) {
        auto tmp = t[0] + t[1] + t[2];
        t[0] = t[1];
        t[1] = t[2];
        t[2] = tmp;
    }

    return t[2];
}

int main() {
    int stairs;
    cin >> stairs;
    for (size_t i = 0; i < stairs; i++) {
        int stp;
        cin >> stp;
        cout << calculate_steps3(stp) << endl;
    }
    return 0;
}