#include <iostream> #include <vector> using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int N; cin >> N; vector<long long> pig(N + 1, 0); vector<long long> alive(N + 1, 0); if (N >= 1) { pig[1] = 1; alive[1] = 1; } for (int day = 2; day <= N; day++) { pig[day] = alive[day - 1] - pig[day - 1]; long long killed = pig[day - 2]; alive[day] = alive[day - 1] + pig[day] - killed; } cout << alive[N] << endl; } return 0; }