#include<bits/stdc++.h> using namespace std; int f(int n){ if(n==1) return 1; if(n==2) return 3; return f(n-1)+f(n-2)+f(n-2); } int main(){ int t,k; cin>>t; for(int i=1;i<=t;i++){ cin>>k; cout<<f(k)<<endl; } return 0; }