Time Limit: 3000 MS Memory Limit: 65536 K

## Description

One day,Jiameier is tidying up the room,and find some coins.
Then she throws the coin to play.Suddenly,she thinks of a
problem ,that if throw n times coin ,how many situations of
no-continuous up of the coin. Hey,Let's solve the problem.
## Input

The first of input is an integer T which stands for the
number of test cases. For each test case, there is one integer
n (1<=n<=1000000000) in a line, indicate the times of throwing coins.
## Output

The number of all situations of no-continuous up of the coin, moduled by 10000.
## Sample Input

3
1
2
3
## Sample Output

2
3
5
## Author

Jiameier
## Source

Sichuan University Programming Contest 2011 Preliminary