C0829 [ZJOI2012]数列

内存限制:256 MB 时间限制:1000 ms

题目描述

小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式:

$A_0=0$

$A_1=1$

$A_{2i}=A_i$(for any integer $i>0$)

$A_{2i+1}=A_i + A_{i+1}$(for any integer $i>0$)

小白作为一个数学爱好者,很快就计算出了这个数列的通项公式。于是,小白告诉小蓝自己已经做出来了,但为了防止小蓝抄作业,小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的,想出了一个绝妙的方法:即让小蓝说一个正整数 $N$,小白则说出的值,如果当 $N$很大时小白仍能很快的说出正确答案,这就说明小白的确得到了公式。但这个方法有一个很大的漏洞:小蓝自己不会做,没法验证小白的答案是否正确。作为小蓝的好友,你能帮帮小蓝吗?

输入格式

输入第一行有且只有一个正整数 $T$,表示测试数据的组数。

第 $2$~$T+1$行,每行一个非负整数$N$。

输出

输出共包含 $T$行。

第 $i$行应包含一个不含多余前缀$0$的数,它的值应等于 $A_n$($n$为输入数据中第$i+1$行被读入的整数)。

样例

样例输入 1

3 1 3 10

样例输出 1

1 2 3

提示

$T \le 20,N \le 10^{100}$