There is a king in the lower left corner of the 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 . The next lines consist of single integer — the size of the board.
For each test case output in a separate line the munber of ways to reach upper right corner of board modulo .