#P1456. 线性递推数列求解

线性递推数列求解

题目描述

在魔法学院的算术课上,教授给学生们展示了一个神奇的数列。这个数列的前两项是固定的魔法值,后续每一项都遵循特定的魔法公式生成:

  • 初始魔法值:F(1) = 0,F(2) = 1
  • 魔法公式:F(n) = 4×F(n-1) - 5×F(n-2)

现在你需要帮助学生们计算这个数列的第n项,以验证他们的魔法计算能力。

输入格式

输入数据第一行是一个正整数T(T<100),表示测试用例的数量。接下来T行,每行一个整数n(2 < n < 50),表示要计算的项数。

输出格式

输出T行,每行对应一个测试用例的结果,即按照魔法公式计算出的F(n)值。

样例

4 
3 
4 
5 
6
4 
11 
24 
41

提示

注意数列的递推关系和初始条件。