P15865 【MX-X26-T1】「Cfz Round 7」feel my soul

きっと誰もが　ずっと探しているの　/　想必每个人都在不停地寻找着 それは偶然ではなくて　偽りの愛なんかじゃなくて　/　那并非偶然　也绝非虚假的爱

Yuki 有一条包含 $n$ 个格子的**环形**纸带，每个格子的编号依次为 $1\sim n$。 Yuki 打算给每个格子染上粉色或蓝色。Yuki 称一种染色方案是「鱼鱼」的，当且仅当： - 对于所有粉色格子，每个粉色格子左右两侧相邻的蓝色格子数量总和相等； - 对于所有蓝色格子，每个蓝色格子左右两侧相邻的粉色格子数量总和相等。 你需要求出「鱼鱼」的染色方案数。定义两种染色方案不同，当且仅当存在不大于 $n$ 的正整数 $i$，满足格子 $i$ 在两种染色方案中所染的颜色不同。

**本题有多组测试数据。** 输入的第一行包含两个整数 $c,t$，分别表示该测试点所属的子任务编号和测试数据组数。样例满足 $c=0$。 接下来依次输入每组测试数据。对于每组测试数据，共一行，包含一个整数 $n$。

对于每组测试数据，输出一行，包含一个整数，表示「鱼鱼」的染色方案数。

### 样例 1 解释 对于第 $1$ 组测试数据，「鱼鱼」的染色方案为粉粉、蓝蓝、粉蓝、蓝粉。 对于第 $2$ 组测试数据，「鱼鱼」的染色方案为粉粉粉、粉粉蓝、粉蓝粉、蓝粉粉、粉蓝蓝、蓝粉蓝、蓝蓝粉、蓝蓝蓝。 对于第 $3$ 组测试数据，「鱼鱼」的染色方案只有全粉和全蓝。 ### 数据范围 对于所有测试数据，均有： - $1 \le t \le 5\cdot 10^5$； - $1\le n \le 10^9$。 **本题采用捆绑测试。** - Subtask 1（12 points）：$T \le 12$，$n \le 12$。 - Subtask 2（32 points）：保证 $n$ 为质数。 - Subtask 3（36 points）：保证 $n$ 为奇数。 - Subtask 4（20 points）：无特殊限制。