def number_of_pigs(N): if N == 1: return 1 # 初始化前两天的猪的数量 pigs = [1, 1, 0] # 从第三天开始计算 for day in range(3, N + 1): # 每天的猪的数量是前一天的猪的数量加上3天前的猪的数量 pigs.append(pigs[day - 1] + pigs[day - 3]) # 返回第N天晚上的猪的数量 return pigs[N] # 读取输入的测试用例数量 T = int(input()) # 对每个测试用例进行处理 for _ in range(T): N = int(input()) print(number_of_pigs(N))