ACoinProblem
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