Ada and Cucumber

Statement

Ada the Ladybug works as farmer. Its season of cucumbers and she wants to harvest them. There lies many cucumbers all around her house. She wants to choose a direction and follow it until all cucumbers in that direction are collected.

Lets consider Ada's house as centerpiece of whole universe, lying on [0,0]. The cucumbers are defined as lines on plane. No cucumber goes through Ada's house (and no cucumber touches it).

How many cucumbers can Ada pick in one go if she chooses the best direction possible?

Input

The first line contains an integer T, the number of test-cases.

Each test-case begins with an integer 1 ≤ N ≤ 105 Afterward N lines follow, with four integers -106 ≤ x1,y1,x2,y2 ≤ 106, the beginning and end of each cucumber. Each cucumber has positive length.

Sum of all N over all test-cases won't exceed 106

Note: Even though cucumber will not go through house, they might touch, intersect or overlap other cucumbers!

Output

For each test-case print one integer - the maximal number of cucumbers which could be picked if Ada chooses a direction and picks every cucumber lying in it.

Example input
5
4
2 1 -1 4
-2 1 1 3
-3 2 0 5
-2 -2 5 1
3
-2 2 -2 -2
2 2 2 -2
-3 -3 -6 -3
3
-2 1 -3 4
3 1 5 5
-2 -2 2 -2
6
-1 5 -6 5
-3 -3 5 -3
-2 -5 5 -5
-1 -6 5 -6
5 1 5 5
6 6 6 -11
3
1 3 4 3
4 2 4 -1
5 1 6 6
	
Example output
3
2
1
4
2
	
Possibly harvested cucumbers
1 2 3
1 3
1
2 3 4 6
2 3
	
Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: SPOJ