Longest Straight Line Path

You are given T test cases. For each test case, you are given an integer N representing the number of points in the plane, followed by N lines, each containing two integers that represent the x and y coordinates of a point.

Your task is to determine the maximum number of points that lie on a single straight line. Two points are considered to be on the same line if the slope between them is the same. In mathematical terms, if the slope between two points (x₁, y₁) and (x₂, y₂) is computed as

\( \text{slope} = \frac{y_2 - y_1}{x_2 - x_1} \)

Note that when computing the slope, you must handle vertical lines and overlapping points appropriately. The greatest common divisor (GCD) is used for normalizing the slope expressed as a pair of integers \( (dx, dy) \). Specifically, you can compute the normalized slope as:

\( \left( \frac{dx}{\gcd(dx,dy)}, \frac{dy}{\gcd(dx,dy)} \right) \)

This challenge tests your understanding of geometry and your ability to work with edge cases such as duplicate points.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N₁
x₁ y₁
x₂ y₂
... 
N₂
x₁ y₁
x₂ y₂
...

Where:

• T is the number of test cases.
• For each test case:
• N is the number of points.
• Followed by N lines of two integers representing the coordinates of each point.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of points that are collinear (lie on the same straight line). The output is written to standard output (stdout).

## sample

5
5
1 1
2 2
3 3
4 5
5 6
4
1 2
4 5
7 8
10 11
3
0 0
0 0
0 0
6
1 2
2 4
3 6
4 8
5 10
6 15
2
1 2
1 3

3
4
3
5
2

</p>