F - Binary Search Tree

A binary search tree (BST) is a tree in which each vertex has at most two children. Each child must be either a left child or a right child of its parent (of course, no vertex can have two left children or two right children). Each vertex of a tree is assigned a key (a value). For each vertex, its key is greater than the key of its left child and all of its posterity, as well as less than the key of its right child and all of its posterity (we consider only trees with unique keys in this task).
To insert a new key into a tree, one has to start in the root and traverse the tree according to the following rules. When the inserted key is less than the key of the current vertex one has to go left, or right otherwise. When one is sent into a place without a vertex, a new vertex is created in this place and is assigned the inserted key. If the tree is empty then the new vertex becomes the root.

Consider an n-vertex binary search tree T containing n keys 1,2,...,n. A permutation p = [p₁,...,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₁,p₂,...,p_n. Find how many permutations are consistent with the tree T. Since results may be very large integers we are interested only in results modulo 32999.

Input Specification

The first line of input contains one positive integer d. This is the number of data sets. The data sets follow. Each set of data occupies two consecutive lines of the input. The first line contains only one integer 1 ≤ n ≤ 30. This is the number of vertices of the tree. The second line contains a sequence of n integers separated by single spaces. The integers are keys in the input tree given in the prefix order (pre-order). In this order, the first integer in the sequence is the key from the root of the tree. It is followed by the keys from the left subtree written in the prefix order. The sequence ends with the keys from the right subtree, also given in the prefix order.

Output Specification

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

Sample Input

5
3
2 1 3
3
1 2 3
1
1
4
2 1 3 4
4
1 4 2 3

Output for the Sample Input

2 
1
1
3
1