新生赛开始了！！

看看你周围有没有已经插好的五颜六色的气球，这些可都是辛劳的学长学姐们晚上一个一个吹出来的。现在就剩红黄蓝没有吹了，那么吹气球的时候问题就来了：

你们的学姐有点强迫症，就是不喜欢黄色，尤其是连续吹黄色的气球：比如上一次吹黄色的气球，下次就要吹一个红色或蓝色的气球，但是如果上一次吹红色或蓝色的气球，下次可以吹一个红色，蓝色或黄色的气球。现在学姐只能吹n个气球（果然是年纪大了）。

这样的话，你能帮学姐算一下一共有多少种满足要求的不同的吹气球颜色顺序吗？

第一行有一个整数T，接下来T组数据，每组数据占1行，第一行是一个整数n（0<n<=40)。题目保证出现的气球足够。

对于每组数据，请输出全部的满足要求的吹气球顺序，输出一行，包含一个整数，每个实例的输出占一行。

2
1
2

3
8