Migrated from Lutece 392 A Coin Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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\leq n\leq 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$.

Samples

3
1
2
3

2
3
5

Resources

10th SCU Programming Contest Final