问题 B: 我叫叶良辰

问题 B: 我叫叶良辰

时间限制: 1 Sec  内存限制: 128 MB
提交: 171  解决: 36
[状态] [讨论版] [提交] [命题人:]
题目描述

果果一直很谦虚,但是良辰还是对他出手了(汗。。

良辰拿出来一个 Pascal 三角形(也叫杨辉三角形。(请不要问是怎么拿出来的。。

我们用一个矩阵来表示 Pascal 三角形

0: C(0, 0)

1: C(1, 0) C(1, 1)

2: C(2, 0) C(2, 1) C(2, 2)

...

其中最左边的数字表示行号。C(x, y) 表示一个组合数,即 x 个元素中取 y 个的方法数。

良辰只有一个问题:Pascal 三角形中的第 n 行有多少个奇数?

这样的问题对于果果来说太水了,于是他把这个问题给了你。

输入

第一行为一个整数 T,表示数据组数。 每组数据只有一行,包含一个整数 n,表示 Pascal 三角形的第 n 行。 T <= 2000,0 <= n <= 2^31。

输出

每组数据输出一行,包含一个整数,表示Pascal 三角形的第 n 行中的奇数个数。

样例输入 Copy
2
0
1
样例输出 Copy
1
2