Upper Right King (Hard)

There is a king in the lower left corner of the n×n checkmate board. The king can move one step right, one step up or one step up-right. How many ways are there for him to reach the upper right corner of the board?

Input

The first line of input contains number T (1 ≤ T ≤ 10000) — the amount of test cases. Next T lines consist of single integer n (1 ≤ n ≤ 10^6) - the size of the board.

Output

For each test case output the munber of ways to reach upper right corner of n×n board modulo 1000003.

Examples