CHASE - A Chase In WonderLand


Alice is in Wonderland. It is March and March Hare is raving mad. It begins to chase Alice. Alice runs as fast as she can, but she comes to the the edge of a quicksand pool. Now this pool has several safe spots where she may comfortably step on without being swallowed by the quicksand. She may step onto any safe spot from solid ground, but thereafter she can jump from spot to spot only in a straight line, and she cant turn back. March Hare is still hot on her heels, so she needs to know the maximum number of jumps she can make.

Input

On the first line there will be a single integer n, denoting the number of test cases. Each test case will consist of a single integer k by itself on a line, followed by k lines containing the x and y co-ordinates of the safe spots, separated by a single space. Both coordinates are integer values. There are no leading or trailing spaces or blank lines. 0 < k ≤ 2200

Output

For each case print a single integer by itself on a line, with no leading or trailing spaces. Do not print blank lines.

Example

Input:
2
5
0 0
1 1
2 2
4 8
2 75
3
0 0
1 2
3 4

Output:
2
1

hide comments
hridoy_089: 2019-05-12 12:37:12

using atan2(y/x) giving wrong answer instead using dy/dx . why?

Last edit: 2019-05-12 12:44:51
sherlock11: 2018-02-02 04:49:35

nice problem..................
do not worry about time complexity
just go with your normal thought

kass_97: 2017-01-14 11:13:30

No IO optimization needed, O(n^2) works fine, killed it in 0.13 sec in first attempt :D

Vipul Srivastava: 2016-02-06 18:21:31

O(k^2) with unordered_map giving TLE..

Yogendra Kumar: 2015-12-09 11:19:03

OMG! O(K^2) is giving TLE in java. I believe this problem is not for java.
My humble request to problem-setters, please exclude JAVA language option from these kind of problems where time limit is too strict that almost no java code can pass it. It's kind of frustrating after investing a lot of time in vain trying solving the problem in java.

Dushyant Singh: 2015-09-12 10:41:50

What is the range of coordinates? Is it exactly same as range of int?

Jaswanth: 2015-08-22 14:33:06

use double do not use float

:(: 2015-04-24 17:12:30

O( N^2 (logN) ) does work... :)

Venkatesh Ganesan: 2014-02-06 14:00:20

very strict time limit. can increase it a bit.

Saurabh Jain: 2013-07-05 12:57:33

AC at one go :) No need to go for IO optimization. scanf() and printf() in C/C++ will suffice to get AC with a good algo.


Added by:Abhilash I
Date:2007-02-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Code Craft 2007