https://www.acmicpc.net/problem/9095
int n, c;
int cnt = 0;
void DFS(int num){
/// num ==0 이라면 원하는 케이스를 찾은 것이므로 cnt를 더해준다
if(num == 0){
cnt++;
return;
}
else{
// 1, 2, 3 으로 표현가능한지 보기
// 지금보니 num-1이 어차피 불가하다면 그 밑에는 할필요가 없게끔 짜도 됨
if(num - 1 >= 0){
DFS(num-1);
}
if(num - 2 >= 0){
DFS(num-2);
}
if(num - 3 >= 0){
DFS(num-3);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin >> c;
for(int k=0; k<c; k++){
cin >> n;
cnt = 0;
DFS(n);
cout<<cnt<<endl;
}
return 0;
}