Cut the rope II

　　We have a rope whose length is L. We will cut the rope into two or more parts, the length of each part must be an integer, and no two parts have the same length.
　　Your task is to calculate there exists how many results after the cutting. We say two results are different if and only if there is at least one part, which we can find in one result but can not find in the other result.

　　There is an integer T (1 <= T <= 50000) in the first line, which indicates there are T test cases in total.
　　For each test case, there is only one integer L (1 <= L <= 50000) which has the same meaning as above.

　　For each test case, you should output the correct answer of the above task in one line.
　　Because the answer may be very large, you should just output the remainder of it divided by 1000000 instead.

3
2
3
6

0
1
3

A Contest to Celebrate Girlfriend's Birthday by Staginner