## ONEXLIS - One X LIS

no tags

For a given sequence a[1], a[2], ... a[n], lets call a subsequence a[k1] ...a[ki]... a[km] (where 1 <= ki <= n and kii+1) as "one X increasing subsequence" if there is exactly one i between 1 and m-1 (inclusive) for which a[ki]>a[ki+1]. Given a sequence find the length of the longest "one X increasing subsequence".

### Input

First line contains t, which denotes the number of test cases. 2*T lines follow. Each test case is described using 2 lines.

First line of a test case contains an integer- n, which denotes the number of elements in the array.

Second lines contains n integers, which represent a[i] 1<=i<=n.

1<=t<=20

1<=n<=100000

1<=a[i]<=10^9

### Output

For each test case, print one integer which represents the number of integers in the One X LIS. The output for each test case should be printed on a new line.

### Example

```Input:
254 3 3 4 155 4 3 2 1
Output:
42```

#### Explanation

In the first test case, the Longest Increasing Subsequence is 3.3.4 whereas the longest One X Subsequence is 4.3.3.4 whose length is 4.

In the second example, any two elements can be chosen to form the longest One X Subsequence, which gives us an answer of 2.