비 단조성

1부터 n까지 정수 n개로 이루어진 길이가 n인 수열 A가 있다. 수열의 각 원소는 서로 다르다. 이때, 다음과 같은 조건을 만족하는 수열 B를 찾으려고 한다.

B[0] > B[1] < B[2] > B[3] < ...

B는 A의 부분 수열이고, 위의 조건을 만족하는 수열 중 가장 길이가 긴 수열이다. 부분 수열이란 수열에서 원소 몇 개를 삭제해서 얻을 수 있는 수열이다. 이때, 순서는 항상 유지되어야 한다.

A가 주어졌을 때, B의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 50이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 다음과 같은 형식이다.

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

n은 최대 30000이다.

각 테스트 케이스에 대해서, B의 길이를 출력한다.