Blocks
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一段长度为n的序列，你有红黄蓝绿4种颜色的砖块，一块砖长度为1，问你铺砖的方案数，其中红色砖和绿色砖的数量必须为偶数。
答案可能很大，请输出后的结果。

输入描述:

第一行包含一个整数，表示T组数据。
每组数据一行，包含一个正整数。

输出描述:

输出一个整数表示答案。
示例1

输入

复制 
2
1
2

输出

复制 
2
6

备注:

原题链接：http://poj.org/problem?id=3734