E. Is this Segment Tree Beats?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tortles recently learned about segment tree beats, which is a segment tree modification that supports range ckmin and ckmax operations in amortized$$$O(\log{n^2})$$$. Tortles decided to play with this funny data structure.

He started with an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ where ($$$1 \le a_i \le 10$$$). He then performed a series of operations over the entire array. In each operation, he chose a number $$$x$$$ between $$$1$$$ and $$$10$$$ and either the operation $$$min$$$ or $$$max$$$. He then set each element $$$a_i$$$ to $$$op(a_i, x)$$$ where $$$op$$$ is the operation he chose.

Unfortunately, after he played around with the array, his computer crashed and he lost his edit history. Given the final array after all operations he performed, how many distinct possibilities are there for the original array $$$a$$$?

Input

The first line will have an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 9$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10$$$) — the values of the final array after all modifications are performed.

Output

For each test case, print the number of possible starting arrays.

Example
Input
1
4
1 4 3 4
Output
49