题目描述

纸上有 $n$ 个点，第 $i$ 个点 $P_i$ 的坐标是 $(i,A_i)$。你可以挑出其中的 $k$ 个点 $P_{i_1},P_{i_2},...,P_{i_k}(1 \le i_1 \lt i_2 \lt ... \lt i_k \le n)$，依次在相邻两个点之间连一条线。为了让这条线美丽，需要存在满足以下条件的 $j$：

• $1 \le j \le k$

• $A_{i_1} \lt A_{i_2} \lt ... \lt A_{i_j} \gt ... \gt A_{i_{k-1}} \gt A_{i_k}$

• $|A_{i_1}-A_{i_2}| \lt |A_{i_2}-A_{i_3}| \lt ... \lt |A_{i_{j-1}}-A_{i_j}|$ 且 $|A_{i_j}-A_{i_{j+1}}| \gt |A_{i_{j+1}}-A_{i_{j+2}}| \gt ... \gt |A_{i_{k-1}}-A_{i_k}|$

你要求出能画出美丽的线的最大的 $k$。

输入

第一行一个整数 $T$ 表示测试数据测组数。

每组测试数据的第一行一个整数 $n$，第二行 $n$ 个整数 $A_1,A_2,...,A_n$。

输出

输出 $T$ 行，每组测试数据一行，一个整数，表示答案。

样例输入 #1

4
5
1 2 3 4 5
9
1 2 4 8 100 8 4 2 1
9
1 7 5 3 1 6 3 9 1
1
1

样例输出 #1

3
9
5
1

样例说明 #1

第一组测试数据，可以选 $1,2,4$ 或者 $1,2,5$，长度为 $3$。

第二组测试数据，可以全部选上。

第三组测试数据，可以选 $1,3,6,3,1$，长度为 $5$。

第四组测试数据，可以选 $1$，长度为 $1$。

数据范围

$1 \le T \le 100$

$1 \le n \le 100$

$0 \le A_i \le 10^9$