| 问题描述 |
|---|
计算斐波那契数列的第n项。 |
| 输入描述 |
第一行是一个正整数T代表测试案例的数量。 每组案例是一个正整数n。(1 <= n <= 1e9) |
| 输出描述 |
针对每组案例，输出斐波那契数列的第n项，然后换行。 由于答案可能很大，所以你只需要输出它对10000取模之后的结果。 |
| 样例输入复制样例 |
4 1 2 3 1000000000 |
| 样例输出 |
1 1 2 6875 |
| 提示说明 |
| 暴力出奇(chao)迹(shi)。 |
| 相关 |