sequence

Time Limit: 1000MS

Memory Limit: 65536KB

Description

将一个给定的数列,拆分成K个不降序列,每个数出现且只出现一次,且在各序列中各个数相对于原数列的相对顺序不变。 如7 6 9 8 10可以拆成 7 9 10和6 8。求最小的K值。

Input

第一行输入一个整数T(1 <= T <= 100),表示接下来T组测试数据, 每组两行,第一行为n,代表数列长度(1<=n<=10000) 接下来一行有n个数,空格分隔(每个数<=50000)。

Output

对每组数据输出一个最小的K值。

Sample Input

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

Sample Output

2
5

Hint

None

Source

None

提交代码