use strict;
use warnings;

our @cache;
sub find {
    my $num = shift;
    if(defined $cache[$num]) {return $cache[$num];}
    if($num == 0) {return 1;}
    if($num < 0) {return 0;}
    
    $cache[$num] = &find($num -1) + &find($num - 2) + &find($num - 3);
    return $cache[$num];
}

my $test_case = <>+0;
for(1..$test_case) {
    my $num = <>+0;
    print &find($num),"\n";
}