#P1473. 递推数列计算

递推数列计算

题目描述

在魔法学院的数学课上,教授给学生们展示了一个神奇的数列。这个数列的生成规则如下:

  • 初始条件:第1项为0,第2项为1
  • 递推公式:第n项 = 4 × 第(n-1)项 - 5 × 第(n-2)项

现在给定多个查询,每个查询给出一个整数n,请你计算出这个数列的第n项的值。

输入格式

输入数据第一行是一个正整数T(T < 10)。接下来T行,每行一个整数n(2 < n < 20)

输出格式

输出有T行,对于输入中每行中的n按照通项计算出F(n)。

样例

4 
3 
4 
5 
6
4 
11 
24 
41

提示

注意递推公式的正确应用