SP71 TREE1 - Tree

Consider an n-vertex binary search tree T containing n keys 1,2,...,n. A permutation p = \[p $ _{1} $ ,...,p $ _{n} $ \] of the integers 1,2,...,n is said to be _consistent with the tree T_ if the tree can be built from the empty one as the result of inserting integers p $ _{1} $ ,p $ _{2} $ ,...,p $ _{n} $ . Find how many permutations are consistent with the tree T.

The first line of the input file contains one positive integer d not larger than 10. This is the number of data sets. The data sets follow. Each set of data occupies two consecutive lines of the input file. The first line contains only one integer n, 1

For each i = 1,...,d, your program should write to the i-th line of output the number of permutations consistent with the tree described in the i-th data set.