This problem is a Mooshak version of a UVA Online Judge Problem.

[PC028] Wavio Sequence

Wavio is a sequence of integers. It has some interesting properties.

• Wavio is of odd length i.e. \(L = 2 \times n + 1\)
• The first \((n + 1)\) integers of Wavio sequence makes a strictly increasing sequence.
• The last \((n + 1)\) integers of Wavio sequence makes a strictly decreasing sequence.
• No two adjacent integers are same in a Wavio sequence.

For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence.

In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence.

For example, if the given sequence is:

1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 5, 4, 1, 2, 3, 2, 2, 1

The longest Wavio subsequence would be 1, 2, 3, 4, 5, 4, 3, 2, 1 so the output should be 9.

Input

The first line of input contains \(t\), the number of test cases

\(t\) lines follow, each containing one test case. Each case starts with \(n\), followed by a sequence of \(n\) integers \(s_1, s_2, \ldots, s_n\).

Output

For each test case, output a line with the length of longest wavio subsequence.

Constraints

• \( 1 \leq t \leq 10 \)
• \( 1 \leq n \leq 20\,000 \)
• \( 1 \leq s_i \leq 10^6 \)

4
10 1 2 3 4 5 4 3 2 1 10
19 1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
5 1 2 3 4 5
8 1 4 5 3 4 6 3 2

9
9
1
5