最长递增点序列

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

有一个2维坐标系(0 < x < = 20, 0 < y < = 20 ),现在给你n ( 0 < n < = 100000 ) 个整数点组成的一个排列,要求求出n个点的一个子集。子集中的点相对位置不能变,且前一个点要小于后一个点。点p1 < 点p2 当且仅当p1.x < = p2.x && p1.y <= p2.y。要求输出这个子集包含的最大点个数。

Input

第一行输入测试数据数目T。 对于每组数据: 3个整数x,y,n 接下来n行每行2个数pi.x,pi.y(都大于等于0,且在方格内))

Output

子集包含的最大点个数。

Sample Input

1
3 3 5
1 1
2 2
1 2
2 1
2 2

Sample Output

3

Hint

Source

沈宇亮

提交代码