Description

至尊大法师——奇异博士，在与灭霸的战斗中，奇异博士幻化出了许多的分身，而奇异博士的分身有很多，但是奇异博士每次分身变换需要时间，为了帮助奇异博士打败灭霸，让我们帮他计算一下这些分身有多少个吧。

奇异博士是个怪人，他可以每一秒进行一次变换，每次分身后分身个数满足这样的一个序列：1,1,2,3,5,8,13,21,34……。（即第一秒是1个，第二秒是1个，第三秒是2个。。。）

给你一个数n，接下来有n次查询，对于每次查询输出经过第m秒钟后分身的个数。由于输出的数会很大，所以请输出结果的后四位即可，对于不足四位需要前补0。

Format

Input

在第一行输入一个数n，表示查询次数 (1<=n<=100)

接下来有n行，每行有一个数m，表示第m秒钟 (1<=m<=10^6)

Output

输出m秒钟后分身的结果，输出结果的后四位即可，对于不足四位需要前补0，每个输出占一行。

Samples

4
1
3
4
5

0001
0002
0003
0005

Hint

样例1：

1表示第1秒钟后分身结果0001（当然是自身咯）

3表示第3秒钟后分身结果0002

4表示第4秒钟后分身结果0003

5表示第5秒钟后分身结果0005

(根据序列的变换得出第m秒钟后分身结果)