22065번 - Интернетопровод 다국어

문제

Популярный во Флатландии интернет-провайдер «Джота» решил расширить свое влияние. Для этого в «Джота» решили провести новый интернетопровод. Интернетопровод можно считать прямой на плоскости.

«Джота» знают, что во Флатландии есть n потенциальных абонентов, i-й абонент живет в доме, расположенном в точке с координатами (x_i, y_i), и в одном доме живет не больше одного абонента. Интернетопровод можно настроить так, что он будет раздавать интернет всем абонентам, которые находятся ровно на некотором выбранном расстоянии от него. Другими словами, если настроить интернетопровод на расстояние d, он будет раздавать интернет тем и только тем абонентам, декартово расстояние от точки, в которой расположен дом абонента, до прямой, задающей интернетопровод, будет равно d.

Помогите инженерам компании «Джота» построить такой интернетопровод, что количество абонентов, охваченных этим интернетопроводом, максимально.

입력

Первая строка содержит одно натуральное число t — число тестовых примеров во входных данных. Далее следуют описания тестов.

Описание каждого теста состоит из нескольких строк. Первая строка содержит одно целое число n (1 ≤ n ≤ 10³) — число абонентов.

Следующие n строк содержат по два целых числа x_i, y_i (−10⁹ ≤ x_i, y_i ≤ 10⁹) — координаты i-го абонента. Гарантируется, что дома никаких двух абонентов не находятся в одной точке.

Сумма n по всем тестам не превосходит 10³.

출력

Выведите одно целое число — максимальное количество абонентов, которое может охватить «Джота».

제한

힌트