#include<iostream>
#include <vector>
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector <pair <int, int> > dp (n+1);	//ends with 0,1
		dp[0] = make_pair(0,0);
		dp[1] = make_pair(1,1);
		for(int i=2; i<=n; i++){
			int endWith1 = dp[i-1].first;
			int endWith0 = dp[i-1].first + dp[i-1].second;
			dp[i] = make_pair(endWith0, endWith1);
		}
		cout << dp[n].first + dp[n].second << endl;
	}
	return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWludCB0OwoJY2luID4+IHQ7Cgl3aGlsZSh0LS0pewoJCWludCBuOwoJCWNpbiA+PiBuOwoJCXZlY3RvciA8cGFpciA8aW50LCBpbnQ+ID4gZHAgKG4rMSk7CS8vZW5kcyB3aXRoIDAsMQoJCWRwWzBdID0gbWFrZV9wYWlyKDAsMCk7CgkJZHBbMV0gPSBtYWtlX3BhaXIoMSwxKTsKCQlmb3IoaW50IGk9MjsgaTw9bjsgaSsrKXsKCQkJaW50IGVuZFdpdGgxID0gZHBbaS0xXS5maXJzdDsKCQkJaW50IGVuZFdpdGgwID0gZHBbaS0xXS5maXJzdCArIGRwW2ktMV0uc2Vjb25kOwoJCQlkcFtpXSA9IG1ha2VfcGFpcihlbmRXaXRoMCwgZW5kV2l0aDEpOwoJCX0KCQljb3V0IDw8IGRwW25dLmZpcnN0ICsgZHBbbl0uc2Vjb25kIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==

MgoyCjM=

2
2
3