비 단조성

$1$부터 $n$까지 서로 다른 정수 $n$개로 이루어진 길이 $n$의 수열 $A$가 있다. 이 수열의 부분 수열 중에서 다음 조건을 만족하는 가장 긴 수열 $B$의 길이를 구하려고 한다.

$B_0 > B_1 < B_2 > B_3 < \cdots$

즉 $B$의 원소는 앞에서부터 차례대로 '크다, 작다, 크다, 작다'를 번갈아 만족해야 하며, 맨 처음 비교는 반드시 '크다'($B_0 > B_1$)여야 한다. 부분 수열이란 원래 수열에서 원소 몇 개를 지우고 남은 수열을 말하며, 남은 원소들의 순서는 그대로 유지된다. 원소가 하나뿐인 수열도 조건을 만족하는 것으로 본다.

$A$가 주어졌을 때 이러한 $B$의 최대 길이를 출력하는 프로그램을 작성하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 50$).

각 테스트 케이스는 한 줄로 이루어지며, 형식은 다음과 같다.

n A[0] A[1] A[2] ... A[n-1]

$n$은 수열의 길이이고 ($1 \le n \le 30000$), 그 뒤에 수열 $A$의 원소 $n$개가 공백으로 구분되어 주어진다. $A$는 $1$부터 $n$까지의 정수를 각각 정확히 한 번씩 포함하는 순열이다.

각 테스트 케이스마다 $B$의 최대 길이를 한 줄에 하나씩 출력한다.