题解

#include<iostream>
using namespace std;

long long f(long long x){
	if(x == 1) return 1;
	else if (x == 2) return 2;
	else return 2*f(x-1) + f(x-2);
}

int main(){
	long long n, x;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> x;
		cout << f(x) << endl;
	}
	return 0;
}