题号：NC200121
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Daxinganling produces a lot of timber. Before loading onto trains, the timber jacks will place the logs to some place within no more than two logs' height first. Looking from the sideway, the figure of a logs stack is as follows:
We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line.
In the figure above, there are 4 logs in the bottom layer of the stack, and 3 logs in the top layer of the stack. So the picture shows one kind of figures with 7 logs accumulated together.
Now, given the total number of logs, Little Gyro wants to know how many possible figures there may be.
In the figure above, there are 4 logs in the bottom layer of the stack, and 3 logs in the top layer of the stack. So the picture shows one kind of figures with 7 logs accumulated together.
Now, given the total number of logs, Little Gyro wants to know how many possible figures there may be.
输入描述:
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤), indicating the number of test cases. For each test case:
Each line contains one integer n (1 ≤ n ≤ 2×), indicating the total number of logs.
输出描述:
For each test case in the input, you should output the corresponding number of possible figures.
Because the number may be very large, just output the number mod 10000.
示例1
说明
In the third sample, you can accumulate 5 logs within such following ways:
First, you can put all the 5 logs at the ground floor.
Then, you can put 4 logs at the bottom layer, and there are 3 positions for the last log to pile up.
After that, you can also put 3 logs at the bottom layer, while the other 2 logs at the top layer.
Above all, you can get 1 + 3 + 1 = 5 figures in order to accumulate 5 logs.