Tèo đang khảo sát một chùm tia laser phát ra từ gốc toạ độ. Mỗi điểm trên mặt phẳng là một mục tiêu mà tia laser có thể bắn trúng. Tèo muốn biết có nhiều nhất bao nhiêu mục tiêu nằm trên cùng một đường thẳng đi qua gốc toạ độ.

Nói cách khác, hãy tìm đường thẳng qua gốc chứa nhiều điểm nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) (\(|x_i|, |y_i| \le 10^6\)). Không có điểm nào trùng với gốc toạ độ.

Định dạng đầu ra

• Một số nguyên duy nhất là số điểm tối đa nằm trên cùng một đường thẳng qua gốc.

Ví dụ

Input:

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

Output:

3

Giải thích: Ba điểm \((1,2), (2,4), (-1,-2)\) cùng nằm trên đường thẳng \(y = 2x\). Các điểm còn lại nằm trên các đường thẳng khác.

Ràng buộc

• Subtask 1 (20 điểm): \(n \le 100\).
• Subtask 2 (30 điểm): \(n \le 10^4\).
• Subtask 3 (50 điểm): \(n \le 10^5\).