说明

Yuki 有一条包含 $n$ 个格子的环形纸带，每个格子的编号依次为 $1\sim n$。

Yuki 打算给每个格子染上粉色或蓝色。Yuki 称一种染色方案是「鱼鱼」的，当且仅当：

• 对于所有粉色格子，每个粉色格子左右两侧相邻的蓝色格子数量总和相等；
• 对于所有蓝色格子，每个蓝色格子左右两侧相邻的粉色格子数量总和相等。

你需要求出「鱼鱼」的染色方案数。定义两种染色方案不同，当且仅当存在不大于 $n$ 的正整数 $i$，满足格子 $i$ 在两种染色方案中所染的颜色不同。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c,t$，分别表示该测试点所属的子任务编号和测试数据组数。样例满足 $c=0$。

接下来依次输入每组测试数据。对于每组测试数据，共一行，包含一个整数 $n$。

输出格式

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

0 8
2
3
5
8
12
40
98
138

4
8
2
8
14
8
4
10

提示

样例 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）：无特殊限制。