statement.md

Problem Statement

平面上に幾つか点(座標は全て整数である)が与えられる。平面上に、最も多くの点を通過するような直線を1本だけ引くとき、通過する点の数を求めよ。

Given some point on a plane surface (coordinate x and y is represented by two integers), calculate the maximum number of points passed by the line which is drawn to pass points as many as possible.

Input

入力は以下の形式で表される。

The input is given with the following format.

D
N1
x11 y11
x12 y12
 :
x1N1 y1N1
N2
x21 y21
x22 y22
:
x2N2 y2N2
:
ND
xD1 yD1
xD2 yD2
:
xDND yDND

ここでDはデータセットの個数である。さらに、i番目のデータセットにおいて、N_iは点の個数、x_ijおよびy_ijはj番目の点の座標である。

D is a number of data sets. For the ith dataset, N_i is the number of points, x_ij and y_ij are a coordinate of jth point.

Constraint

入力は以下の条件をすべて満たす。

• 1 <= D <= 100
• 1 <= i <= D を満たすすべての整数iについて、
  • 2 <= N_i <= 50
  • さらに、1 <= j, k <= N_i を満たすすべての整数j, kについて、
    • -100 <= x_ij <= 100
    • -100 <= y_ij <= 100
  • j ≠ k ならば (x_ij, y_ij) ≠ (x_ik, y_ik)

The input satisfies the following constraints.

• 1 <= D <= 100

• For i satisfying 1 <= i <= D
  • 2 <= N_i <= 50
  • For j satisfying 1 <= j, k <= N_i
    • -100 <= x_ij <= 100
    • -100 <= y_ij <= 100
  • if j ≠ k then (x_ij, y_ij) ≠ (x_ik, y_ik)

Output

出力は、各データセットごとに直線が通過する点の個数を1行で出力せよ。

Write the maximum number of points passed by a line with respect to each data set.

Sample Input

2
5
0 0
-1 -1
1 1
2 2
3 -3
6
5 0
0 -2
0 1
0 7
1 3
2 4

Sample Output

4
3