题解

题面描述

给定一个函数 $f$，满足：

• $f(0)=1$；
• 对任意非负整数 $n$，有
  • 若 $x=2n$，则 $f(x)=f(n)$；
  • 若 $x=2n+1$，则 $f(x)=2\,f(n)$。

题目内容

定义函数 $f(x)$满足以下递归关系: $1.f(0)=1$;

$2.$对于任意非负整数$n$，有$f(2n)=f(n)$;

$3.$对于任意非负整数$n$，有$f(2n +1)= f(n) ×2$

现给定若干次询问，每次询问一个非负整数$x$，请你计算$f(x)$ 的值.

输入描述

第一行输入一个整数 $q(1≦q≦10^5)$，表示询问的次数

接下来$q$行，每行输入一个非负整数$x(0≦x≦10^9)$，表示一次询问。

输出描述

对于每个询问，输出一行一个整数，表示$f(x)$的值.

样例1

输入

3
0 
1 
3

输出

1
2
4

说明

对于$x=0$，由定义有$f(0)=1$。

对于$x=1$，可以表示为$2·0+1$.故

• $f(1)=f(0)×2=1×2=2$。

对于$x=3$，可以表示为$2·1+1$，故

• $f(3)=f(1) ×2=2×2=4$

样例2

输入

2
2
7

输出

2
8

说明

对于$x=2$，可以写作$2×1$，故

• $f(2) =f(1) = 2$;

对于$x=7$，可以写作$2·3+1$且

• $f(3) = f(1)×2=2×2=4$
• 故$f(7) = f(3)×2=4×2=8$