North East King

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

Input

The first line contains the number of test cases $t(1\le t\le 1000)$. The next $t$ lines consist of single integer $n(1\le n\le 1000)$ — the size of the board.

Output

For each test case output in a separate line the munber of ways to reach upper right corner of $n\times n$ board modulo $1000003$.

Examples