1219:斐波那契数列-2

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

计算斐波那契数列的第n项。

输入

第一行是一个正整数T代表测试案例的数量。

每组案例是一个正整数n。(1 <= n <= 1e9)

输出

针对每组案例,输出斐波那契数列的第n项,然后换行。

由于答案可能很大,所以你只需要输出它对10000取模之后的结果。

样例输入

4

1

2

3

1000000000

样例输出

1

1

2

6875

HINT
暴力出奇(chao)迹(shi)。
来源
TKK-ICPC Round#1