在一无限大的二维平面中，我们做如下假设： 
1、  每次只能移动一格； 
2、  不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）； 
3、  走过的格子立即塌陷无法再走第二次；

求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。

3

7

/*/

中文题，有点类似以前做过的小蜜蜂那题，规定一个方向后只能沿着三个方向去移动了。

所以每次移动只有3种方向可以走，而且还要标记是否已经走过这条路，所以思路很清楚直接DFS。

但是DFS会TLE，输入的数字在1~20，数据不多，直接打表。

AC代码：

/*/

#include"map"

#include"cmath"

#include"string"

#include"cstdio"

#include"vector"

#include"cstring"

#include"iostream"

#include"algorithm"

using namespace std;

typedef long long LL;

const int MX=202;

#define memset(x,y) memset(x,y,sizeof(x))

#define FK(x) cout<<"【"<<x<<"】"<<endl

int step,ans;

bool vis[MX][MX];

int ans2[22]= {0,3,7,17,41,99,239,577,1393,3363,8119,19601,47321,114243,275807,665857,1607521,3880899,9369319,22619537,54608393,0};

//因为DFS全部计算后会超时，而且输入只有1-20，所以直接打出全部的数表

void DFS(int dir,int x,int y,int tot) {

	if(tot==step) {       //如果步数已经达到了就计数。

//	FK("YES"<<x<<","<<y<<","<<tot);  //确认

		ans++;

		return ;

	}

	for(int i=1; i<=3; i++) {

		if(i==1)x++;       //每种情况对应的位移。

		if(i==2)y++;

		if(i==3)x--;

		if(!vis[x][y]) {

			vis[x][y]=1;//标记已经塌陷的路

			tot++;

			DFS(i,x,y,tot);

			vis[x][y]=0;

			tot--;

		}

		if(i==1)x--;

		if(i==2)y--;

		if(i==3)x++;

	}

}

int main() {

	int T,x;

	scanf("%d",&T);

	while(T--) {

		scanf("%d",&x);/*这里是打表之后加上的*/

//	for(step=1; step<=20; step++) {

//		ans=0;

//		memset(vis,0);

//			vis[100][100]=1;//起点已经塌陷

//			for(int i=1; i<=3; i++) {

//				int xx=100,yy=100;//起点开始，向三个可行方向去深搜

//				if(i==1)xx++;

//				if(i==2)yy++;

//				if(i==3)xx--;

//				vis[xx][yy]=1;//标记路已经塌陷

//				DFS(i,xx,yy,1);

//				vis[xx][yy]=0;

//

//			}

			printf("%d\n",ans2[x]);

//		}

	}

	return 0;

}