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