收成【鱼CR2】

题目描述

农夫知道了农田的相关数据，自然能求出 $n$ 天后的收成是多少了

但是！

因为农夫数学不好，所以想让你帮忙算一算，其中，计算方式如下：

设现在有 $a$ 棵麦子，如果当前麦子数为奇数，那么下一年的麦子就是本年收成的 $2$ 倍，否则，下一年的麦子就是今年麦子的 $2$ 倍多一个

形式化的说：

给你一个数字 $n$，问你：$f_i = f_{i-1}\times 2 + i \%2, f_i = 1$ 中 $f_n$ 等于多少？

输入格式

多测题，格式如下：

T
case1
case2
...
caseT

对于每个 case:

n

输出格式

格式有点特殊，你需要一行就把 $T$ 个数字都输出完，以空格隔开

注意，不要有行末空格

样例 #1

样例输入 #1

5
3
9
2
7
5

样例输出 #1

5 341 2 85 21

提示

样例解释

推算出： $f_1 = 1, f_2 = 2, f_3 = 5, f_4 = 10, f_5 = 21, f_6 = 42, f_7 = 85, f_8 = 170, f_9 = 341$

数据范围

因为是多测题，所以我们只设置 $4$ 个测试点，分数数据设置如下：

编号	$data$	分值
1	$T=100, n <= 10$	$10$
2	$T=100,$ $n<=100$	$20$
3	$T=10000,$ $n<=500$	$30$
4	$T<=10000, n <= 2000$	$40$

本题设置为 200ms 的原因是：

1. Python的暴力法可以在 800ms 以内通过第四个测试点
2. Python的递推法可以在 100ms 以内通过
3. C++搭配O2可以在 20ms 内跑出来

因此，请各位选手把你的代码效率压缩到极致，这也考大家的代码功底