Chef Counts SemiBSTs

Everyone has heard of binary search trees or BSTs. A BST is a rooted tree, such that the root has atmost two children. The subtree rooted at each of root's children should be valid BSTs. All the values in the left subtree should be smaller than the root and all the values in the right subtree should be larger than the root.
However, there's a new data structure in town called semiBST. Formally, a semiBST is a tree with N nodes which satisfies the following conditions:
 Each node contains a distinct value.
 The root has at most two children.
 The right subtree of the root (if it exists) is a valid semiBST.
 The left subtree of the root (if it exists) is any unordered rooted tree. That is, the children of a vertex are not ordered, and hence no concept of left or right child.
 The BST property for the root is maintained, i.e. all the values in the left subtree of the root are lesser than that of the root and all the values in the right subtree of the root are greater than that of the root.
For example, let us show that tree shown above is a semiBST. The root of the tree is 5. All the elements in the left subtree are smaller than 5 and all the elements in the right subtree are greater than 5.
Now, all we need to show is that the right subtree is a valid semiBST:
We are now considering the subtree rooted at 8, and hence the current root is 8. All the elements in the left subtree are smaller than 8 and all the elements in the right subtree (which doesn't exist) are greater than 8. Hence the subtree rooted at 8 is a valid semiBST. And hence the entire tree, rooted at 5 is a valid semiBST.
Given N, find the number of semiBSTs having exactly N nodes, and such that all the N values in the nodes are from {1, 2, ..., N}. Output the answer modulo 663224321.
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first and only line of each test case contains a single integer N denoting the number of nodes.
Output
For each test case, print a single line containing one integer — the number of semiBSTs modulo 663224321.
Constraints
 1 ≤ T ≤ 100000
 1 ≤ N ≤ 100000
Example 1
Input: 4 1 2 3 4 Output: 1 2 5 18
Author:  satyaki3794 
Editorial  https://discuss.codechef.com/problems/MANCBST 
Tags  acm17chn, chn17rol, fft, medhard, satyaki3794 
Date Added:  30112017 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH 3.6, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, kotlin, PERL6, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions