题目背景

凤栖梧桐，梧桐树种在大大小小的山丘上……

题目描述

凤有 $n$ 座山丘，为了足不出丘就能体验四季轮回，凤凰决定将每座山丘装饰成春，夏，秋，冬四季中的一种。为了四季轮换正常，要求春和冬的个数为偶数。现在凤想知道有多少种方案。

输入格式

第一行为 $t$，代表数据组数。接下来 $t$ 行每行包括一个数字 $n$，代表有 $n$ 座山。

输出格式

$t$ 行，每行输出方案数。

样例

2
1
2

2
6

数据范围

• 对于 $30\%$ 的数据，$n\le 30$。
• 对于全部数据，$1\le T\le 5$，$1\le n\le 1.5\times 10^4$，保证输出小于 $10^{10^4}$。