问题 E: Out of Control

There is a cloud service API to help user store history timestamps. The data structure for each user is initially an empty stack. Every time you post a request to the API with an integer $x$, denoting the current timestamp, the service will append $x$ to the end of the stack. When $x$ is less than the previous timestamp stored in the stack, the service will think the input is wrong, and will append the previous timestamp instead of $x$.

You have posted the API for $n$ times, your request timestamp is xi in the $i$-th call. However, the network is out of control. The service may receive your requests in any arbitrary order, and may even miss some requests. Knowing this issue, you are asking for the on-call engineer to have a look at your stack in the database. Assume the service received exactly $k$ requests, how many possible distinct stacks will it be?

The first line contains a single integer $T$ ($1\le T\le 100$), the number of test cases. For each test case:

The first line of the input contains a single integer $n$ ($1\le n\le 3,000$), denoting the total number of requests.

The second line contains $n$ integers x1,x2,…,xn (1≤xi≤1e9), denoting the timestamp of each request.

It is guaranteed that the sum of all $n$ is at most $30,000$.

2
3
1 2 3
3
2 3 3

3
5
5
2
2
2