Problem D: 统计方案
Memory Limit：32 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：6
Solved：4
Description
在一无限大的二维平面中，我们做如下假设：
1、每次只能移动一格；
2、不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、走过的格子立即塌陷无法再走第二次。
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
1、每次只能移动一格；
2、不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、走过的格子立即塌陷无法再走第二次。
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
Input
首先给出一个正整数C，表示有C组测试数据。
接下来的C行，每行包含一个整数n（n<=20），表示要走n步。
接下来的C行，每行包含一个整数n（n<=20），表示要走n步。
Output
请编程输出走n步的不同方案总数；
每组的输出占一行。
每组的输出占一行。
Sample Input Copy
2
1
2Sample Output Copy
3
7HINT
第n步的方案数f(n) = 2*f(n-1) + f(n-2)。这个是怎么来的呢？用a(n)表示第n步向上走的方案数，b(n)表示第n步左右走的方案数。那么a(n) = a(n-1) + b(n-1) (在这里为什么b(n-1)不能乘以2呢？因为向左走向右走不能同时具备)。b(n) = 2*a(n-1) + b(n-1) （a(n-1)*2是因为如果第n-1步向上走，那么第n步它可以选择向左走或向右走，这两种方案可是同时成立。对于b(n-1)，因为如果第n-1步你朝了一个方向走,那么第n步你只能继续朝这个方向走）
f(n)=a(n)+b(n)=a(n-1)+b(n-1)+2*a(n-1)+b(n-1)=3*a(n-1)+2*b(n-1)
=2*f(n-1)+a(n-1)=2*f(n-1)+a(n-2)+b(n-2)=2*f(n-1)+f(n-2)