#include <stdio.h>
#include <string>
#include <iostream>
#include <string.h>
#include <map>
#define MAX 30
using namespace std;
/*
	一道很好的递推题，虽然思路是从discuss中获得，但是应该想简单些，从前一次走可获得，
	每次向上走可以为下一次获得3步机会，而向左或者向右则只能由两种。
*/
int main()
{
	int two[MAX] = {0,2}, three[MAX] = {0,1}, result[MAX] = {0,3};
	for(int i=2; i<=20; i++)
	{
		two[i] = two[i-1] + three[i-1] *2;
		three[i] = three[i-1] + two[i-1];
		result[i] = two[i-1] * 2 + three[i-1] * 3;
	}
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		printf("%d\n", result[n]);
	}
	return 0;
}
/*
Problem Description
在一无限大的二维平面中，我们做如下假设：
1、  每次只能移动一格；
2、  不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、  走过的格子立即塌陷无法再走第二次；
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
 
Input
首先给出一个正整数C，表示有C组测试数据
接下来的C行，每行包含一个整数n (n<=20)，表示要走n步。
 
Output
请编程输出走n步的不同方案总数；
每组的输出占一行。
 
Sample Input
2
1
2
 
Sample Output
3
7
*/

附件列表