A probabilitic preorder traversal is generated for a binary search tree from the following pseudo-code
function preorder(u) {
if u is null then return
print u.label
r = either 0 or 1 with 50% probability
if r == 0
preorder(u.left_child)
preorder(u.right_child)
if r == 1
preorder(u.right_child)
preorder(u.left_child)
}
Given the preorder traversals of a binary search tree you can always uniquely construct the binary search tree. Since, the inorder traversal of a binary search tree is of course, the sorted list of labels.
Given one of the probabilistic preorder traversals of some binary search tree, print the number of different probabilitic preorder traversals that the above algorithm might generate. See the explanation section for clarity.
Input
The fist line in input is equal to N, the number of test cases. Then follows the description of N test cases. The first line in each test case is the integer N, the number of nodes in the binary search tree. On the next line there are N integers - a probabilistic preorder traversal of the binary search tree. All the labels of the nodes in a test case will be distinct. The value of each label in a test case will be between 1 and N, inclusive. You may assume that the input will be a valid probabilistic preorder traversal of some binary search tree.
Output
For each test case, print a single number on a line by itself. This number should be the number of different probabilistic preorder traversals that exist for the binary search tee - including the one given in the test case. You may assume that the answer will always be less than or equal to 1,000,000,000. In fact, it is easy to see that the answer can never be more than 2^30 (read to-the-power).
Constraints
1 < T ≤ 10000
1 ≤ N ≤ 30
Sample Input
3
3
2 1 3
3
1 2 3
5
2 4 3 5 1
Sample Output
2
1
4
Explanation
In the first test case the two possible traversals are (2 1 3) and (2 3 1).
In the second test case there is only one possible traversal and that is the one given.
In the third test case the four possible traversals are (2 1 4 3 5), (2 1 4 5 3), (2 4 3 5 1) and (2 4 5 3 1).