题目

桑哥到底认不认识猫猫

桑哥和猫猫认识在斐波那契学院，在那个学院里面，所有的东西都是用斐波那契数字命名的，当然猫猫除外，因为猫猫可爱。

斐波那契学院校训如下：斐波那契数列$F_0$ = $0$ , $F_1$ = $1$ , $F_n$ = $F_{n-1}$ + $F_{n-2}$ ;

“哦!我亲爱的普罗米修斯，我的上帝啊!”(播音腔)猫猫

“亲爱的桑哥呀一一，您这是发生了什么事情，导致您变成现在这个样子，啊!”(播音腔)猫猫

“哦!亲爱的...呃..先(生) ...哦!不!女士!我并没有发生什么重大的事情，只是出了一点点比较重大的车祸而已!您不必太过关心我!”(内心os:这jb猫是谁呀? )桑哥

“哦!怎么回事(低声啜泣)，桑哥... (哽咽)你...你怎么..不认识我了....呜鸣呜呜鸣...”猫猫做西子捧心状哭倒在病床上。

“哦!亲爱的女士，您这是怎么了，快，快起来，你压到我的瘸掉的腿了。”桑哥

猫猫立即起身;

“女士，听您的描述，咱们俩之前是旧识!医生说，我车祸碰伤了脑袋，现在可能记不清一一些人和事，还请您不要介意，您来看我，我是真的非常高兴。”桑哥做丽丽磕头状。

猫猫听完之后，表情如下看着桑哥|

几把猫很担心你

虽然但是猫猫并不相信桑哥，因为桑哥总是欺骗可爱的它，为了检验桑哥是否欺骗了猫猫，猫猫打算用在学院学习的知识考桑哥； 猫猫打算让桑哥输出F(n) mod 1e4。

Format

Input

输入t，t行。 每行输入一个n

$1\leq t\leq 1e6$ . $0\leq n\leq 1e18$ .

Output

输出n行，每行输出$F_n$ mod 1e4

Samples

4
0
9
999999999
1000000000

0
34
626
6875

Limitation

1s, 1024KiB for each test case.