计算斐波那契数列的第n项。
第一行是一个正整数T代表测试案例的数量。
每组案例是一个正整数n。(1 <= n <= 1e9)
针对每组案例,输出斐波那契数列的第n项,然后换行。
由于答案可能很大,所以你只需要输出它对10000取模之后的结果。
4
1
2
3
1000000000
6875