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