DIVCON - Divide and Conquer

no tags 

Anne and Brenda found some cookies scattered on the lattice points in the 2D coordinate system. They agreed to divide them in the following manner.

First, Anne draws a vertical line (that is, a line with the equation x = c, for any real number c) somewhere in the plane. Then Brenda draws a horizontal line (y = d) somewhere in the plane. Now they have divided the plane in four quadrants.

Anne gets all the cookies lying in the upper right and the lower left quadrant, and Brenda gets all the cookies lying in the upper left and the lower right quadrant. Cookies which lie on the vertical or the horizontal line are ignored.

Anne's goal is to maximize the number of cookies she gets, knowing that Brenda plays optimally (in order to maximize her number of cookies).

Input

In the first line of input there is an integer T (1 ≤ T ≤ 600), the number of test cases.

Each test case starts with an integer N (1 ≤ N ≤ 1000), the number of cookies. In the next N lines there are coordinates (Xi, Yi) of the cookies, integers in the interval [1, 1000]. There can be multiple cookies at the same point.

Output

For each of the T cases, output in a separate line the maximal number of cookies Anne can surely get.

Example

Input:
2
5
1 1
4 1
4 5
5 1
3 3
11
7 10
7 11
7 10
7 11
6 6
5 5
4 8
1 5
1 6
1 4
7 1
Output: 2
5

hide comments
sagar_ghai: 2015-01-19 22:47:14

any leads here ?? a direction maybe?

Adrian Satja Kurdija: 2014-08-07 11:57:26

@HELLO: real.

HELLO: 2014-08-07 11:57:26

problem setter or someone please tell me here d is an integer or real no

Tony Beta Lambda: 2014-08-07 11:57:26

@Ashrut: x = 5.5

Last edit: 2011-07-13 09:03:46
Ashrut Tewari: 2014-08-07 11:57:26

I m getting answer 4 for test case 2, can anybody explain how is it 5 ? Which column is selected by Anne ?


Added by:Stjepan
Date:2010-04-26
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6
Resource:authors: Filip Pavetić, Adrian Satja Kurdija