Maximum Collinear Points

You are given a set of 2D points and your task is to find the maximum number of points that lie on a single straight line. Two or more points are said to be collinear if they all lie on the line described by the equation $$y = mx + c$$. In other words, for any three points \((x_1,y_1)\), \((x_2,y_2)\) and \((x_3,y_3)\) to be collinear, the following must hold:

$$ (y_2 - y_1)(x_3 - x_1) = (y_3 - y_1)(x_2 - x_1) $$

Given multiple test cases, determine the maximum number of collinear points for each test case.

inputFormat

The input is given on standard input. The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains an integer (n), the number of points. Then (n) subsequent lines follow; each line contains two space-separated integers (x) and (y) representing the coordinates of a point.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of collinear points found among the given set of points.## sample

1
5
1 1
2 2
3 3
4 5
5 6

3