#include<iostream> using namespace std; int a[1000000000]; int main() { int n; cin>>n; for(int i=0;i<n;i++){ int m; cin>>m; a[1]=1; a[2]=2; for(int i=0;i<=m-3;i++){ a[i+3]=2*a[i+2]+a[i+1]; } cout<<a[m]<<endl; } return 0; }