[Zjoi2012]数列(sequence)

小白和小蓝一起上数学课。下课后，老师布置了一道作业：求下面这个数列的通项公式。

A_0=0,\qquad A_1=1,

A_{2n}=A_n,\qquad A_{2n+1}=A_n+A_{n+1}\quad(n\ge 0).

作为数学爱好者，小白很快就计算出了这个数列的通项公式。为了向小蓝证明自己确实完成了这道题，同时又不直接公布公式，小白想出了一个办法：由小蓝给出一个非负整数 $N$ ，小白则回答 $A_N$ 的值。如果当 $N$ 很大时，小白仍能迅速给出正确答案，就说明他确实得到了通项公式。

然而，小蓝自己不会做这道题，因此无法验证小白的答案是否正确。请你帮助小蓝计算 $A_N$ 。

输入格式

第一行包含一个正整数 $T$ ，表示测试数据的组数。

接下来 $T$ 行，每行包含一个非负整数 $N$ 。

输出共 $T$ 行。

第 $i$ 行输出对应的 $A_N$ ，其中 $N$ 为输入中的第 $i+1$ 行。输出的数不得包含多余的前导零。

1
2
3

本题为 ZJOI 2012 试题「数列」，题面与测试数据整理自 BZOJ。

1
2
3