Devo! She has broken up with him again!

And after a series of break ups and patch ups, she is done with him!

Being a geek to keep herself distracted, she picks up her favourite topic of dynamic programming where she comes across this idiot problem which says:

Given a integer N, you have to tell the sum of number of structurally unique binary search trees built on different permutations of the set {x, x such that x belongs to [1, N] and x is an integer}.

A binary search tree is said to be built on a permutation iff the in-order traversal of that BST is same as the permutation.

A permutation is said to be distinct from another if there exists a position i such that the i'th element of the permutations is different.

Now, her inability to solve the problem is quite stressful to her! Help her in solving the problem!

Note: She observes that this number can be very large so output this number modulo 1908.

Moreover she tells you that there in-order traversal of a binary search tree is unique.

For binary search tree read Wikipedia's binary search tree.

Input

The first line of the input consists of T, the number of test cases.

The following T lines consists of a single integer N.

(N can be at max 1000, T can be at max 1000)

Output

You have to output T lines each consisting of the answer to the problem modulo 1908.

Example

Input:
2
1
2

Output:
1
2