题目描述

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

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

输入格式

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

第$2\sim T+1$行，每行一个非负整数$N$。

输出格式

输出文件共包含$T$行。

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

样例

3
1
3
10

1
2
3

数据范围与约定

对于$100\%$的数据：$T\le 20,N\le 10^{100}$.

附件

image2:file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.png