母牛递推

　　

为情所困退学在家的钱哥毅然决定养猪！

在2010年1月1日，他买了一只刚出生的母猪幼仔，假设每只小母猪从第3个年头开始，每年的第一天都会生出4只小母猪，同时，钱哥会在每年的12月31日售出所有差一天就要年满5周岁的猪。

请计算：在第N年（2010年是第1年，2011是第2年，依次类推）的今天（5月4日），钱哥的养猪场会存栏多少只猪?

Input

输入数据第一行是一个整数T(0<T<=40)，表示测试数据的组数.
接下来有T行，每行有一个数N(0<N<=40)表示一组测试数据，其含义如题目描述。

Output

对于每个测试实例，请输出在第N年的今天母猪的数量，每组数据的输出占一行。

Sample Input

3
2
3
5

Sample Output

1
5
29

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//
#define inf 0x3f3f3f3f
const int N=100;
const int M=1000;
ll f[N];int main()
{int test,n;ll a[40+5]={0,1,0,4,4};ll sum[40+5]={0,1,1,5,9};rep(i,5,45){a[i]=(a[i-2]+a[i-3]+a[i-4])*4;sum[i]=sum[i-1]+a[i]-a[i-5];}int cas;RI(cas);while(cas--){int x;RI(x);cout<<sum[x]<<endl;}
}