Definition

In this problem, a sequence $a_1 \ldots a_n$ of length at least 2 satisfying the following conditions is called a super rich kadomatsu sequence.

• All elements of the sequence are distinct
• $\min_{i\in \text{even}}a_i \gt \max_{i\in\text{odd}}a_i$ or $\max_{i\in\text{even}}a_i \lt \min_{i\in\text{odd}}a_i$

The original definition comes from No.122 Trends and Countermeasures: Kadomatsu Sequence (Part 3), but note that it has been extended to sequences of arbitrary length.
Also, this definition differs from that of a kadomatsu sequence sequence. $1,3,2,5,4$ satisfies the conditions of a kadomatsu sequence sequence, but does not satisfy the conditions of a super rich kadomatsu sequence.

Problem Statement

Among the subsequences (not necessarily contiguous) of the permutation $P_1\ldots P_N$ that satisfy the conditions of a super rich kadomatsu sequence, output the length of the longest one.

Input

$T$ test cases are given at once. $(1 \le T \le 10^5)$

$T$
$\text{TestCase}_1$
$\vdots$
$\text{TestCase}_T$

Each test case is given in the following format.

$N$
$P_1$ $\ldots$ $P_N$

• $3 \le N \le 5\times 10^5$
• $1 \le P_i \le N$
• $P_i \neq P_j , (i \neq j)$

Output

For each test case, output the answer, separated by newlines.

Sample

3
5
1 4 3 2 5
5
2 1 3 5 4
6
1 2 3 4 5 6

4
3
2