Description

给定一个长度为N的整数数组, 请计算该数组中最长非降了序列长度。

Input

第一行输入M(M<=10)表示有M组数据。每组数据输入N(N<=10000), 接下来输入N个整数。

Output

输出M行正整数，第i行表示第i组数据的长非降了序列长度。

Sample Input

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

Sample Output

3
5