LOVEBIRDS - She was in Love with BST


Devo! She has broken up with him again!Frown

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 both 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 https://en.wikipedia.org/wiki/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

hide comments
priyank: 2015-08-18 17:08:29

@psych_cod3r my 700B source length code in java get accepted. Here normal solution will give tle, some optimization is needed. My code get accepted in 0.15 seconds :) In java scanner gives time limit error.

=> (y) thanx for sharing the info. my solution takes 0.15s with no optimisations so i made it 0.15s

Last edit: 2015-08-20 18:07:09
newbie: 2015-08-18 10:50:09

how can be the inorder of a BST be any purmutation other than 1,2,3,4......n

EDIT(psych_cod3r): If it so then you have to only print the number of structurally unique BSTs built on this permutation.

Last edit: 2015-08-18 12:04:25

Added by:psych_cod3r
Date:2015-08-17
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA
Resource:Intuition