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.

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)

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.

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

8
7
7

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