There is a king in the lower left corner of the n × n chess 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 - the amount of test cases. Next T lines consist of single integer n - the size of the board.

Constraints

1 <= T <= 10000
1 <= n <= 1000000

Output

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

Example

Input:
2
2
3

Output:
3
13