#include <iostream> #include <vector> using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int N; cin >> N; // 使用动态规划思想 // pig[i] 表示第i天晚上猪的数量 // newPig[i] 表示第i天新出生的猪数量 vector<long long> pig(N + 1, 0); vector<long long> newPig(N + 1, 0); if (N >= 1) { pig[1] = 1; // 第一天买了一头刚出生的猪 newPig[1] = 1; } for (int day = 2; day <= N; day++) { // 今天的新猪数量 = 昨天所有能生育的猪数量 // 能生育的猪 = 昨天的猪 - 昨天刚出生的猪 newPig[day] = pig[day - 1] - newPig[day - 1]; // 今天的猪数量 = 昨天的猪 + 今天新出生的猪 - 今天被杀掉的猪 // 被杀掉的猪 = 两天前刚出生的猪数量(它们今天生了第二头小猪) if (day >= 3) { pig[day] = pig[day - 1] + newPig[day] - newPig[day - 2]; } else { pig[day] = pig[day - 1] + newPig[day]; } } cout << pig[N] << endl; } return 0; }