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 diagonally one step up-right. How many ways are there for him to reach the upper right corner of the board?
The first line contains the number of test cases t (1≤t≤1000). The next t lines consist of single integer n (1≤n≤1000) — the size of the board.
For each test case output in a separate line the munber of ways to reach upper right corner of n×n board modulo 1000003.