文理学院程序设计在线练习


判断曲线上的点

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 236   Accepted Submission(s): 106
Problem Description

已知函数f(x)在区间[0,10000]上严格单调递增,对于给定的n个点的坐标(xi,yi) ,其中 0<=x0<x1<...<xi<...<xn<=10000, 请判断这n个点中,最多有多少个点可能落在函数f(x)上.

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。对于每组测试数据,第一行是正整数n (1<=n<=100), 表示点的总数,第二行有2*n个整数,表示需要处理的n个点的坐标。格式为x1 y1 x2 y2 x3 y3 ... xn yn.

Output

对于每组测试,输出可能落在函数f(x)上的最大可能的点数。

Sample Input
3
4
1 1 3 1 4 2 5 5
3
3 3 4 4 5 5
7
2 8 3 9 5 1 6 9 7 3 8 5 9 7
Sample Output
3
3
4
Author

flx

Source

zscas第二届程序设计竞赛2008/03/30下午