1063:铺瓷砖-2

对于一个3行m列的走道。现在用1*3、2*3、3*3的砖去铺满，一共有多少种不同的铺法（1*3的砖可以旋转成3*1，同理2*3可以旋转成3*2）。
以下是一个3行10列的一种铺法：

1个正整数n，表示测试案例的数量。
每组测试案例中，有一个正整数m，表示走道是m列的。（m<=100）

针对每组案例，输出一个数字，表示不同的铺法的数量，要求精确输出（值可能比long long int还长，但不会超过10的100次方）。每组案例输出后都要换行。

3
1
3
50

1
7
177822624501049026