Đàn kiến thẳng hàng

Là chúa tể của quân đoàn kiến, việc của bạn là sắp xếp quân đoàn của mình phải chiến đấu cùng với nhau. Quân đoàn của bạn có \(N\) chiến binh kiến, chiến binh kiến thứ \(i\) đang ở tọa độ \((X_{i}, Y_{i})\). Muốn quân đoàn kiến sát cánh chiến đấu càng nhau, các chiến binh kiến phải di chuyển sao cho \(N\) chiến binh đứng cùng trên một đường thẳng trên mặt phẳng tọa độ \(Oxy\). Có tối thiểu bao nhiêu chiến binh kiến phải di chuyển để quân đoàn kiến nằm cùng trên một đường thẳng ?

Tất nhiên, do một số lý do cá nhân, bạn không cần thiết phải tìm ra kết quả chính xác, bởi vì số lượng kiến có thể rất lớn. Nếu số lượng tối thiểu các chiến binh kiến phải di chuyển là \(M\), mọi kết quả từ \(M\) đến \(2 \times M\) đều được chấp nhận. Tất nhiên, nếu bạn tìm ra được chính xác \(M\), là một điều rất tốt !

Input

• Dòng đầu tiên là số nguyên \(T\) - số trường hợp cần phải giải quyết.
• \(T\) trường hợp tiếp theo được nhập theo cấu trúc sau đây :
• Dòng đầu tiên là số nguyên dương \(N\) \((1 \leq N \leq 10^6)\) - số lượng chiến binh kiến của quân đoàn.
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(X_{i}, Y_{i}\) \((|X_{i}|, |Y_{i}| \leq 10^9)\).

Tổng \(N\) trong các truy vấn không vượt quá \(10^6\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) là kết quả của trường hợp thứ \(i\).

Example

3
4
1 1
2 2
-3 -3
4 4
4
1 1
-1 1
1 -1
-1 -1
7
4 8
2 4
7 2
6 10
0 1
3 4
4 7

0
2
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(20\).
• Subtask \(2\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(300\).
• Subtask \(3\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(1000\).
• Subtask \(4\) (\(25\%\) số điểm) : không có ràng buộc gì thêm.