定義

本問題では、以下を満たす長さ2以上の数列 $a_1 \ldots a_n$ をスーパーリッチ門松列列と呼ぶことにします。

• 数列の要素は全て異なる
• $\min_{i\in \text{偶数}}a_i \gt \max_{i\in\text{奇数}}a_i$ または $\max_{i\in\text{偶数}}a_i \lt \min_{i\in\text{奇数}}a_i$

定義のオリジナルはNo.122 傾向と対策：門松列（その３）ですが、 任意の長さの数列に拡張されている点に注意してください。
また、本定義は門松列列とは異なります。$1,3,2,5,4$ は門松列列の条件を満たしますが、スーパーリッチ門松列列の条件を満たしません。

問題文

順列 $P_1\ldots P_N$ のスーパーリッチ門松列列を満たす部分列（連続しなくても良い）のうち、最長のものの長さを出力してください。

入力

$T$ 個のテストケースが同時に与えられます。$(1 \le T \le 10^5)$

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

各テストケースは以下のフォーマットに従って与えられます。

$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)$

出力

各テストケースごとに、解となる値を改行区切りで出力してください。

サンプル

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

4
3
2