### Bai Hao Wanna Have A Girl Friend

#### Problem Description

Winter is coming, and Bai Hao feels so cold. He wanna have a girl friend to warm his hand, so he asks master UMR to help him hold a beauty contest.

Now there're * n* candidates standing in one line. But Bai Hao doesn't like a sequence with different heights.

In order to satisfy Bai Hao, UMR decides to choose some of them to form a new sequence which their height is neither ascending nor descending.

UMR wants to know the number of possible schemes.

**Note**: If two girls with same height stand in different position, we consider them as only one scheme.

#### Input

The first line of input contains an integer *T* (0 < *T* < 100), indicating the number of test cases.

For each case:

- The first line contains an integer
*n,*denoting there're*n*candidates (1 <=*n*< 10^5) - Next line contains
*n*integers separated by spaces, denoting the height of each candidate*hi*(1 <=*hi*<= 10^5)

#### Output

For each case, output an integer in one line, indicating the number of schemes.

The value of each output will not exceed the range of *int*.

#### Sample Input

3 4 160 170 170 170 5 165 170 175 175 170 3 100 100 100

#### Sample Output

8 7 7

#### Hint

For the first sample input, UMR has 8 schemes (represented as the position of each candidate in original sequence):

1

2

3

4

2 3

2 4

3 4

2 3 4